Developer CD Series 1996 May: Tool Chest

home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 May: Tool Chest / Developer CD Series May 1996 (Tool Chest) (Apple Computer) (1996).iso / Tool Chest / Development Tools & Languages / Macintosh Common Lisp Related / User Contributions / btree.sea / btree / btree.lisp < prev next >
MacBinary | 1992-08-12 | 51.9 KB | [TEXT/CCL2]
open in:
MacOS 8.1 extracted |
Win98 extracted |
DOS extracted
browse contents |
view JSON data |
view as text

This file was processed as: MacBinary (archive/macBinary).
Confidence	Program	Detection	Match Type	Support
`10%`	dexvert	MacBinary `(archive/macBinary)`	fallback	Supported
`1%`	dexvert	Text File `(text/txt)`	fallback	Supported
`100%`	file	MacBinary II, inited, Wed Aug 12 14:52:21 1992, modified Wed Aug 12 14:52:21 1992, creator Common Lisp 2, type ASCII, 52452 bytes "btree.lisp" , at 0xcd64 505 bytes resource	default (weak)
`99%`	file	data	default
`74%`	TrID	Macintosh plain text (MacBinary)	default
`25%`	TrID	MacBinary 2	default (weak)
`100%`	siegfried	fmt/1762 MacBinary (II)	default
`100%`	lsar	MacBinary	default
id metadata
key	value
macFileType	`[TEXT]`
macFileCreator	`[CCL2]`
hex view
+--------+-------------------------+-------------------------+--------+--------+
|00000000| 00 0a 62 74 72 65 65 2e | 6c 69 73 70 00 00 00 00 |..btree.|lisp....|
|00000010| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 54 45 58 54 43 43 4c | 32 01 00 00 00 00 00 00 |.TEXTCCL|2.......|
|00000050| 00 00 00 00 00 cc e4 00 | 00 01 f9 a6 af 0e 65 a6 |........|......e.|
|00000060| af 0e 65 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |..e.....|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 81 81 9e ca 00 00 |........|........|
|00000080| 28 69 6e 2d 70 61 63 6b | 61 67 65 20 3a 62 74 72 |(in-pack|age :btr|
|00000090| 65 65 29 0d 0d 3b 3b 3b | 3b 3b 3b 3b 3b 3b 3b 3b |ee)..;;;|;;;;;;;;|
|000000a0| 3b 3b 3b 3b 3b 3b 3b 3b | 3b 3b 3b 3b 3b 3b 3b 3b |;;;;;;;;|;;;;;;;;|
|000000b0| 3b 3b 3b 3b 3b 3b 3b 3b | 3b 3b 3b 3b 3b 3b 3b 3b |;;;;;;;;|;;;;;;;;|
|000000c0| 3b 3b 3b 3b 3b 3b 3b 3b | 3b 3b 3b 3b 3b 3b 3b 3b |;;;;;;;;|;;;;;;;;|
|000000d0| 3b 3b 3b 3b 3b 3b 3b 3b | 3b 3b 3b 3b 3b 3b 3b 0d |;;;;;;;;|;;;;;;;.|
|000000e0| 3b 3b 20 62 74 72 65 65 | 2e 6c 69 73 70 0d 3b 3b |;; btree|.lisp.;;|
|000000f0| 0d 3b 3b 20 43 6f 70 79 | 72 69 67 68 74 20 a9 20 |.;; Copy|right . |
|00000100| 31 39 39 32 20 55 6e 69 | 76 65 72 73 69 74 79 20 |1992 Uni|versity |
|00000110| 6f 66 20 54 6f 72 6f 6e | 74 6f 2c 20 44 65 70 61 |of Toron|to, Depa|
|00000120| 72 74 6d 65 6e 74 20 6f | 66 20 43 6f 6d 70 75 74 |rtment o|f Comput|
|00000130| 65 72 20 53 63 69 65 6e | 63 65 0d 3b 3b 20 41 6c |er Scien|ce.;; Al|
|00000140| 6c 20 52 69 67 68 74 73 | 20 52 65 73 65 72 76 65 |l Rights| Reserve|
|00000150| 64 0d 3b 3b 0d 3b 20 61 | 75 74 68 6f 72 3a 20 4d |d.;;.; a|uthor: M|
|00000160| 61 72 6b 20 41 2e 20 54 | 61 70 69 61 20 6d 61 72 |ark A. T|apia mar|
|00000170| 6b 74 40 64 67 70 2e 74 | 6f 72 6f 6e 74 6f 2e 65 |kt@dgp.t|oronto.e|
|00000180| 64 75 20 6f 72 20 6d 61 | 72 6b 74 40 64 67 70 2e |du or ma|rkt@dgp.|
|00000190| 75 74 6f 72 6f 6e 74 6f | 2e 63 61 0d 3b 3b 20 0d |utoronto|.ca.;; .|
|000001a0| 3b 3b 20 50 61 63 6b 61 | 67 65 20 66 6f 72 20 6d |;; Packa|ge for m|
|000001b0| 61 6e 69 70 75 6c 61 74 | 69 6e 67 20 62 61 6c 61 |anipulat|ing bala|
|000001c0| 6e 63 65 64 20 61 76 6c | 20 74 72 65 65 73 2e 0d |nced avl| trees..|
|000001d0| 3b 3b 0d 3b 3b 20 41 63 | 6b 6e 6f 77 6c 65 64 67 |;;.;; Ac|knowledg|
|000001e0| 65 6d 65 6e 74 73 3a 0d | 3b 3b 0d 3b 3b 20 52 65 |ements:.|;;.;; Re|
|000001f0| 76 69 73 69 6f 6e 20 68 | 69 73 74 6f 72 79 3a 0d |vision h|istory:.|
|00000200| 3b 3b 0d 3b 3b 20 57 6f | 72 6b 20 74 6f 20 64 6f |;;.;; Wo|rk to do|
|00000210| 3a 0d 3b 3b 20 20 20 53 | 75 70 70 6f 72 74 20 74 |:.;;   S|upport t|
|00000220| 72 65 65 2d 6d 65 72 67 | 69 6e 67 20 61 6e 64 20 |ree-merg|ing and |
|00000230| 63 6f 6e 63 61 74 65 6e | 61 74 69 6f 6e 20 28 61 |concaten|ation (a|
|00000240| 6e 20 65 6e 74 69 72 65 | 20 74 72 65 65 20 69 73 |n entire| tree is|
|00000250| 20 74 6f 20 62 65 20 69 | 6e 73 65 72 74 65 64 0d | to be i|nserted.|
|00000260| 3b 3b 20 20 20 74 6f 20 | 74 68 65 20 72 69 67 68 |;;   to |the righ|
|00000270| 74 20 6f 66 20 61 6e 20 | 65 78 69 73 74 69 6e 67 |t of an |existing|
|00000280| 20 74 72 65 65 29 2e 0d | 3b 3b 20 20 0d 3b 3b 20 | tree)..|;;  .;; |
|00000290| 57 69 74 68 69 6e 20 61 | 76 6c 2d 74 72 65 65 2c |Within a|vl-tree,|
|000002a0| 20 6f 72 64 65 72 2d 66 | 75 6e 63 74 69 6f 6e 20 | order-f|unction |
|000002b0| 69 73 20 61 20 66 75 6e | 63 74 69 6f 6e 20 6f 66 |is a fun|ction of|
|000002c0| 20 74 77 6f 20 61 72 67 | 75 6d 65 6e 74 73 20 28 | two arg|uments (|
|000002d0| 75 20 76 29 0d 3b 3b 20 | 72 65 66 6c 65 63 74 69 |u v).;; |reflecti|
|000002e0| 6e 67 20 61 20 74 6f 74 | 61 6c 20 6f 72 64 65 72 |ng a tot|al order|
|000002f0| 69 6e 67 20 6f 6e 20 74 | 68 65 20 6b 65 79 73 2e |ing on t|he keys.|
|00000300| 0d 3b 3b 20 54 68 65 20 | 76 61 6c 75 65 20 72 65 |.;; The |value re|
|00000310| 74 75 72 6e 65 64 20 69 | 73 20 6f 6e 65 20 6f 66 |turned i|s one of|
|00000320| 20 7b 2a 65 71 75 61 6c | 2a 2c 20 2a 62 65 66 6f | {*equal|*, *befo|
|00000330| 72 65 2a 2c 20 2a 61 66 | 74 65 72 2a 7d 0d 3b 3b |re*, *af|ter*}.;;|
|00000340| 20 20 20 77 68 65 6e 20 | 28 75 20 3d 20 76 29 2c |   when |(u = v),|
|00000350| 20 28 6f 72 64 65 72 2d | 66 75 6e 63 74 69 6f 6e | (order-|function|
|00000360| 20 75 20 76 29 20 3d 20 | 2a 65 71 75 61 6c 2a 0d | u v) = |*equal*.|
|00000370| 3b 3b 20 20 20 20 20 20 | 20 20 28 75 20 3c 20 76 |;;      |  (u < v|
|00000380| 29 2c 20 28 6f 72 64 65 | 72 2d 66 75 6e 63 74 69 |), (orde|r-functi|
|00000390| 6f 6e 20 75 20 76 29 20 | 3d 20 2a 62 65 66 6f 72 |on u v) |= *befor|
|000003a0| 65 2a 0d 3b 3b 20 20 20 | 20 20 20 20 20 28 75 20 |e*.;;   |     (u |
|000003b0| 3e 20 76 29 2c 20 28 6f | 72 64 65 72 2d 66 75 6e |> v), (o|rder-fun|
|000003c0| 63 74 69 6f 6e 20 75 20 | 76 29 20 3d 20 2a 61 66 |ction u |v) = *af|
|000003d0| 74 65 72 2a 0d 3b 3b 0d | 3b 3b 20 20 54 68 65 20 |ter*.;;.|;;  The |
|000003e0| 61 6c 67 6f 72 69 74 68 | 6d 73 20 61 72 65 20 62 |algorith|ms are b|
|000003f0| 61 73 65 64 20 6f 6e 20 | 74 68 65 20 62 61 6c 61 |ased on |the bala|
|00000400| 6e 63 65 64 20 74 72 65 | 65 20 61 6c 67 6f 72 69 |nced tre|e algori|
|00000410| 74 68 6d 73 20 69 6e 20 | 4b 6e 75 74 68 0d 3b 3b |thms in |Knuth.;;|
|00000420| 20 20 54 68 65 20 41 72 | 74 20 6f 66 20 43 6f 6d |  The Ar|t of Com|
|00000430| 70 75 74 65 72 20 50 72 | 6f 67 72 61 6d 6d 69 6e |puter Pr|ogrammin|
|00000440| 67 2c 20 53 65 61 72 63 | 68 69 6e 67 20 61 6e 64 |g, Searc|hing and|
|00000450| 20 53 6f 72 74 69 6e 67 | 20 56 6f 6c 75 6d 65 20 | Sorting| Volume |
|00000460| 49 49 49 0d 3b 3b 20 20 | 73 65 63 74 69 6f 6e 73 |III.;;  |sections|
|00000470| 20 36 2e 32 2e 32 20 2d | 20 36 2e 32 2e 34 20 77 | 6.2.2 -| 6.2.4 w|
|00000480| 69 74 68 20 6d 6f 64 69 | 66 69 63 61 74 69 6f 6e |ith modi|fication|
|00000490| 73 2e 0d 3b 3b 20 0d 3b | 3b 20 20 54 68 65 20 62 |s..;; .;|;  The b|
|000004a0| 61 6c 61 6e 63 65 64 20 | 74 72 65 65 73 20 61 72 |alanced |trees ar|
|000004b0| 65 20 72 65 64 2d 62 6c | 61 63 6b 20 74 72 65 65 |e red-bl|ack tree|
|000004c0| 73 20 61 75 67 6d 65 6e | 74 65 64 20 77 69 74 68 |s augmen|ted with|
|000004d0| 20 70 6f 69 6e 74 73 20 | 74 6f 0d 3b 3b 20 20 61 | points |to.;;  a|
|000004e0| 6c 6c 6f 77 20 66 61 73 | 74 20 72 65 70 6f 72 74 |llow fas|t report|
|000004f0| 69 6e 67 20 61 6e 64 20 | 75 70 64 61 74 69 6e 67 |ing and |updating|
|00000500| 2e 20 54 68 65 20 72 65 | 70 72 65 73 65 6e 74 61 |. The re|presenta|
|00000510| 74 69 6f 6e 20 69 73 20 | 64 65 73 63 72 69 62 65 |tion is |describe|
|00000520| 64 20 69 6e 0d 3b 3b 20 | 20 43 68 65 6e 67 20 53 |d in.;; | Cheng S|
|00000530| 57 20 61 6e 64 20 4a 61 | 6e 61 72 64 6f 6e 20 52 |W and Ja|nardon R|
|00000540| 2c 20 22 45 66 66 69 63 | 69 65 6e 74 20 6d 61 69 |, "Effic|ient mai|
|00000550| 6e 74 65 6e 61 6e 63 65 | 20 6f 66 20 74 68 65 20 |ntenance| of the |
|00000560| 75 6e 69 6f 6e 20 69 6e | 74 65 72 76 61 6c 73 20 |union in|tervals |
|00000570| 0d 3b 3b 20 20 6f 6e 20 | 61 20 6c 69 6e 65 2c 20 |.;;  on |a line, |
|00000580| 77 69 74 68 20 61 70 70 | 6c 69 63 61 74 69 6f 6e |with app|lication|
|00000590| 73 22 2c 20 50 72 6f 63 | 65 65 64 69 6e 67 73 20 |s", Proc|eedings |
|000005a0| 6f 66 20 74 68 65 20 46 | 69 72 73 74 20 41 6e 6e |of the F|irst Ann|
|000005b0| 75 61 6c 20 41 43 4d 2d | 53 49 41 4d 20 0d 3b 3b |ual ACM-|SIAM .;;|
|000005c0| 20 20 53 79 6d 70 6f 73 | 69 75 6d 20 6f 6e 20 44 |  Sympos|ium on D|
|000005d0| 69 73 63 72 65 74 65 20 | 41 6c 67 6f 72 69 74 68 |iscrete |Algorith|
|000005e0| 6d 73 2c 20 53 49 41 4d | 20 70 70 37 34 2d 38 33 |ms, SIAM| pp74-83|
|000005f0| 2e 0d 3b 3b 0d 3b 3b 20 | 20 54 68 65 20 61 64 64 |..;;.;; | The add|
|00000600| 69 74 69 6f 6e 61 6c 20 | 66 69 65 6c 64 73 20 61 |itional |fields a|
|00000610| 72 65 20 6d 61 72 6b 65 | 64 20 77 69 74 68 20 61 |re marke|d with a|
|00000620| 6e 20 61 73 74 65 72 69 | 73 6b 20 28 2a 29 0d 3b |n asteri|sk (*).;|
|00000630| 3b 0d 3b 3b 20 20 47 69 | 76 65 6e 20 61 20 62 74 |;.;;  Gi|ven a bt|
|00000640| 72 65 65 20 72 65 63 6f | 72 64 20 66 6f 72 20 61 |ree reco|rd for a|
|00000650| 20 6e 6f 6e 2d 6e 75 6c | 6c 20 6e 6f 64 65 20 76 | non-nul|l node v|
|00000660| 2c 20 74 68 65 20 66 6f | 6c 6c 6f 77 69 6e 67 20 |, the fo|llowing |
|00000670| 66 69 65 6c 64 73 20 61 | 72 65 20 64 65 66 69 6e |fields a|re defin|
|00000680| 65 64 0d 3b 3b 20 20 2a | 20 20 20 6d 69 6e 20 20 |ed.;;  *|   min  |
|00000690| 20 20 20 2d 20 65 69 74 | 68 65 72 20 61 20 70 6f |   - eit|her a po|
|000006a0| 69 6e 74 65 72 20 74 6f | 20 74 68 65 20 6c 65 66 |inter to| the lef|
|000006b0| 74 6d 6f 73 74 20 6c 65 | 61 66 20 6f 66 20 74 68 |tmost le|af of th|
|000006c0| 65 20 73 75 62 74 72 65 | 65 0d 3b 3b 20 20 20 20 |e subtre|e.;;    |
|000006d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 6f 72 20 6e |        |    or n|
|000006e0| 69 6c 20 69 66 20 76 20 | 69 73 20 74 68 65 20 6c |il if v |is the l|
|000006f0| 65 66 74 6d 6f 73 74 20 | 6e 6f 64 65 20 6f 66 20 |eftmost |node of |
|00000700| 74 68 65 20 74 72 65 65 | 20 72 6f 6f 74 65 64 20 |the tree| rooted |
|00000710| 61 74 20 76 0d 3b 3b 20 | 20 2a 20 20 20 6d 61 78 |at v.;; | *   max|
|00000720| 20 20 20 20 20 2d 20 65 | 69 74 68 65 72 20 61 20 |     - e|ither a |
|00000730| 70 6f 69 6e 74 65 72 20 | 74 6f 20 74 68 65 20 72 |pointer |to the r|
|00000740| 69 67 68 74 6d 6f 73 74 | 20 6c 65 61 66 20 6f 66 |ightmost| leaf of|
|00000750| 20 74 68 65 20 73 75 62 | 74 72 65 65 0d 3b 3b 20 | the sub|tree.;; |
|00000760| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 6f |        |       o|
|00000770| 72 20 6e 69 6c 20 69 66 | 20 76 20 69 73 20 74 68 |r nil if| v is th|
|00000780| 65 20 72 69 67 68 74 6d | 6f 73 74 20 6e 6f 64 65 |e rightm|ost node|
|00000790| 20 6f 66 20 74 68 65 20 | 74 72 65 65 20 72 6f 6f | of the |tree roo|
|000007a0| 74 65 64 20 61 74 20 76 | 0d 3b 3b 20 20 20 20 20 |ted at v|.;;     |
|000007b0| 20 6b 65 79 20 20 20 20 | 20 2d 20 74 68 65 20 6b | key    | - the k|
|000007c0| 65 79 20 61 73 73 6f 63 | 69 61 74 65 64 20 77 69 |ey assoc|iated wi|
|000007d0| 74 68 20 76 0d 3b 3b 20 | 20 20 20 20 20 76 61 6c |th v.;; |     val|
|000007e0| 20 20 20 20 20 2d 20 74 | 68 65 20 76 61 6c 75 65 |     - t|he value|
|000007f0| 20 61 73 73 6f 63 69 61 | 74 65 64 20 77 69 74 68 | associa|ted with|
|00000800| 20 74 68 65 20 6b 65 79 | 20 6b 65 79 20 6f 66 20 | the key| key of |
|00000810| 76 0d 3b 3b 20 20 20 20 | 20 20 6c 65 66 74 20 20 |v.;;    |  left  |
|00000820| 20 20 2d 20 61 20 70 6f | 69 6e 74 65 72 20 74 6f |  - a po|inter to|
|00000830| 20 74 68 65 20 6c 65 66 | 74 20 63 68 69 6c 64 72 | the lef|t childr|
|00000840| 65 6e 20 6f 66 20 76 0d | 3b 3b 20 20 20 20 20 20 |en of v.|;;      |
|00000850| 72 69 67 68 74 20 20 20 | 2d 20 61 20 70 6f 69 6e |right   |- a poin|
|00000860| 74 65 72 20 74 6f 20 74 | 68 65 20 72 69 67 68 74 |ter to t|he right|
|00000870| 20 63 68 69 6c 64 72 65 | 6e 20 6f 66 20 76 0d 3b | childre|n of v.;|
|00000880| 3b 20 20 20 20 20 20 62 | 61 6c 61 6e 63 65 20 2d |;      b|alance -|
|00000890| 20 74 68 65 20 62 61 6c | 61 6e 63 65 20 66 61 63 | the bal|ance fac|
|000008a0| 74 6f 72 20 6f 66 20 74 | 68 65 20 72 6f 6f 74 65 |tor of t|he roote|
|000008b0| 64 20 73 75 62 74 72 65 | 65 20 76 0d 3b 3b 20 20 |d subtre|e v.;;  |
|000008c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 2a 62 |        |      *b|
|000008d0| 61 6c 61 6e 63 65 64 2a | 20 20 20 20 20 2d 20 74 |alanced*|     - t|
|000008e0| 68 65 20 72 69 67 68 74 | 20 61 6e 64 20 6c 65 66 |he right| and lef|
|000008f0| 74 20 62 72 61 6e 63 68 | 65 73 20 61 72 65 20 65 |t branch|es are e|
|00000900| 71 75 61 6c 20 69 6e 20 | 68 65 69 67 68 74 0d 3b |qual in |height.;|
|00000910| 3b 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |;       |        |
|00000920| 20 2a 72 69 67 68 74 2d | 74 61 6c 6c 65 72 2a 20 | *right-|taller* |
|00000930| 2d 20 74 68 65 20 72 69 | 67 68 74 20 62 72 61 6e |- the ri|ght bran|
|00000940| 63 68 20 69 73 20 6f 6e | 65 20 6c 65 76 65 6c 20 |ch is on|e level |
|00000950| 74 61 6c 6c 65 72 20 74 | 68 61 6e 20 74 68 65 20 |taller t|han the |
|00000960| 6c 65 66 74 0d 3b 3b 20 | 20 20 20 20 20 20 20 20 |left.;; |        |
|00000970| 20 20 20 20 20 20 20 2a | 6c 65 66 74 2d 74 61 6c |       *|left-tal|
|00000980| 6c 65 72 2a 20 20 2d 20 | 74 68 65 20 6c 65 66 74 |ler*  - |the left|
|00000990| 20 62 72 61 6e 63 68 20 | 69 73 20 6f 6e 65 20 6c | branch |is one l|
|000009a0| 65 76 65 6c 20 74 61 6c | 6c 65 72 20 74 68 61 6e |evel tal|ler than|
|000009b0| 20 74 68 65 20 72 69 67 | 68 74 0d 3b 3b 0d 0d 28 | the rig|ht.;;..(|
|000009c0| 65 76 61 6c 2d 77 68 65 | 6e 20 28 65 76 61 6c 20 |eval-whe|n (eval |
|000009d0| 63 6f 6d 70 69 6c 65 29 | 0d 20 20 28 72 65 71 75 |compile)|.  (requ|
|000009e0| 69 72 65 20 27 62 74 72 | 65 65 2d 64 65 63 6c 29 |ire 'btr|ee-decl)|
|000009f0| 0d 20 20 28 72 65 71 75 | 69 72 65 20 27 6d 61 63 |.  (requ|ire 'mac|
|00000a00| 72 6f 73 29 29 0d 0d 28 | 70 72 6f 76 69 64 65 20 |ros))..(|provide |
|00000a10| 27 62 74 72 65 65 29 0d | 0d 28 65 78 70 6f 72 74 |'btree).|.(export|
|00000a20| 20 27 28 61 64 64 2d 6e | 6f 64 65 0d 20 20 20 20 | '(add-n|ode.    |
|00000a30| 20 20 20 20 20 20 64 65 | 6c 65 74 65 2d 6e 6f 64 |      de|lete-nod|
|00000a40| 65 0d 20 20 20 20 20 20 | 20 20 20 20 66 69 6e 64 |e.      |    find|
|00000a50| 2d 70 61 74 68 0d 20 20 | 20 20 20 20 20 20 20 20 |-path.  |        |
|00000a60| 66 69 6e 64 2d 6b 65 79 | 0d 20 20 20 20 20 20 20 |find-key|.       |
|00000a70| 20 20 20 2a 63 6f 70 79 | 2d 62 74 72 65 65 0d 20 |   *copy|-btree. |
|00000a80| 20 20 20 20 20 20 20 20 | 20 64 69 72 65 63 74 2d |        | direct-|
|00000a90| 66 69 6e 64 2d 6b 65 79 | 0d 20 20 20 20 20 20 20 |find-key|.       |
|00000aa0| 20 20 20 70 72 69 6e 74 | 2d 70 61 74 68 0d 20 20 |   print|-path.  |
|00000ab0| 20 20 20 20 20 20 20 20 | 70 72 69 6e 74 2d 74 72 |        |print-tr|
|00000ac0| 65 65 0d 20 20 20 20 20 | 20 20 20 20 20 66 72 6f |ee.     |     fro|
|00000ad0| 6d 2d 62 74 72 65 65 6b | 0d 20 20 20 20 20 20 20 |m-btreek|.       |
|00000ae0| 20 20 20 72 6f 6f 74 2d | 70 61 74 68 0d 20 20 20 |   root-|path.   |
|00000af0| 20 20 20 20 20 20 20 74 | 6f 2d 62 74 72 65 65 6b |       t|o-btreek|
|00000b00| 0d 20 20 20 20 20 20 20 | 20 20 20 69 73 2d 6c 65 |.       |   is-le|
|00000b10| 61 66 0d 20 20 20 20 20 | 20 20 20 20 20 6d 61 78 |af.     |     max|
|00000b20| 2d 76 61 6c 0d 20 20 20 | 20 20 20 20 20 20 20 6d |-val.   |       m|
|00000b30| 69 6e 2d 76 61 6c 0d 20 | 20 20 20 20 20 20 20 20 |in-val. |        |
|00000b40| 20 2a 74 6f 2d 62 74 72 | 65 65 0d 20 20 20 20 20 | *to-btr|ee.     |
|00000b50| 20 20 20 20 20 67 65 74 | 2d 6e 65 78 74 2d 6e 6f |     get|-next-no|
|00000b60| 64 65 0d 20 20 20 20 20 | 20 20 20 20 20 6f 70 65 |de.     |     ope|
|00000b70| 72 61 74 65 2d 6f 6e 2d | 74 72 65 65 0d 20 20 20 |rate-on-|tree.   |
|00000b80| 20 20 20 20 20 20 20 66 | 69 6e 64 2d 72 6f 6f 74 |       f|ind-root|
|00000b90| 29 20 3a 62 74 72 65 65 | 29 0d 0d 0d 28 73 65 74 |) :btree|)...(set|
|00000ba0| 66 20 2a 70 72 69 6e 74 | 2d 63 69 72 63 6c 65 2a |f *print|-circle*|
|00000bb0| 20 74 29 0d 0d 28 64 65 | 66 70 61 72 61 6d 65 74 | t)..(de|fparamet|
|00000bc0| 65 72 20 2a 64 65 62 75 | 67 2a 20 6e 69 6c 29 0d |er *debu|g* nil).|
|00000bd0| 0d 28 64 65 66 75 6e 20 | 69 73 2d 64 65 62 75 67 |.(defun |is-debug|
|00000be0| 20 28 29 0d 20 20 2a 64 | 65 62 75 67 2a 29 0d 0d | ().  *d|ebug*)..|
|00000bf0| 3b 3b 3b 20 6d 61 63 72 | 6f 73 0d 0d 28 64 65 66 |;;; macr|os..(def|
|00000c00| 6d 61 63 72 6f 20 66 6f | 75 6e 64 2d 6e 6f 64 65 |macro fo|und-node|
|00000c10| 20 28 6e 65 77 2d 6e 6f | 64 65 20 70 61 74 68 29 | (new-no|de path)|
|00000c20| 0d 20 20 60 28 70 75 73 | 68 20 28 6c 69 73 74 20 |.  `(pus|h (list |
|00000c30| 2a 65 71 75 61 6c 2a 20 | 2c 6e 65 77 2d 6e 6f 64 |*equal* |,new-nod|
|00000c40| 65 29 20 2c 70 61 74 68 | 29 29 0d 0d 28 64 65 66 |e) ,path|))..(def|
|00000c50| 6d 61 63 72 6f 20 72 6f | 6f 74 2d 70 61 74 68 20 |macro ro|ot-path |
|00000c60| 28 72 6f 6f 74 29 0d 20 | 20 22 41 20 70 61 74 68 |(root). | "A path|
|00000c70| 20 63 6f 6e 73 69 73 74 | 69 6e 67 20 6f 66 20 74 | consist|ing of t|
|00000c80| 68 65 20 72 6f 6f 74 20 | 6f 66 20 74 68 65 20 74 |he root |of the t|
|00000c90| 72 65 65 22 0d 20 20 60 | 28 77 68 65 6e 20 2c 72 |ree".  `|(when ,r|
|00000ca0| 6f 6f 74 0d 20 20 20 20 | 20 28 6c 69 73 74 20 28 |oot.    | (list (|
|00000cb0| 6c 69 73 74 20 2a 65 71 | 75 61 6c 2a 20 2c 72 6f |list *eq|ual* ,ro|
|00000cc0| 6f 74 29 29 29 29 0d 0d | 28 64 65 66 6d 61 63 72 |ot))))..|(defmacr|
|00000cd0| 6f 20 73 65 6c 65 63 74 | 20 28 65 78 70 20 26 62 |o select| (exp &b|
|00000ce0| 6f 64 79 20 62 6f 64 79 | 29 0d 20 20 28 6c 65 74 |ody body|).  (let|
|00000cf0| 20 28 28 76 61 72 20 28 | 67 65 6e 73 79 6d 29 29 | ((var (|gensym))|
|00000d00| 20 63 6f 64 65 20 63 6f | 6e 64 69 74 69 6f 6e 29 | code co|ndition)|
|00000d10| 0d 20 20 20 20 28 64 6f | 6c 69 73 74 20 28 66 72 |.    (do|list (fr|
|00000d20| 61 67 20 62 6f 64 79 29 | 0d 20 20 20 20 20 20 28 |ag body)|.      (|
|00000d30| 73 65 74 66 20 63 6f 6e | 64 69 74 69 6f 6e 20 28 |setf con|dition (|
|00000d40| 6e 74 68 20 30 20 66 72 | 61 67 29 29 0d 20 20 20 |nth 0 fr|ag)).   |
|00000d50| 20 20 20 28 70 75 73 68 | 0d 20 20 20 20 20 20 20 |   (push|.       |
|00000d60| 28 63 6f 6e 73 0d 20 20 | 20 20 20 20 20 20 28 69 |(cons.  |      (i|
|00000d70| 66 20 28 6d 65 6d 62 65 | 72 20 63 6f 6e 64 69 74 |f (membe|r condit|
|00000d80| 69 6f 6e 20 27 28 74 20 | 6f 74 68 65 72 77 69 73 |ion '(t |otherwis|
|00000d90| 65 29 29 0d 20 20 20 20 | 20 20 20 20 20 20 74 0d |e)).    |      t.|
|00000da0| 20 20 20 20 20 20 20 20 | 20 20 28 6c 69 73 74 20 |        |  (list |
|00000db0| 27 65 71 75 61 6c 20 76 | 61 72 20 63 6f 6e 64 69 |'equal v|ar condi|
|00000dc0| 74 69 6f 6e 29 29 0d 20 | 20 20 20 20 20 20 20 28 |tion)). |       (|
|00000dd0| 72 65 73 74 20 66 72 61 | 67 29 29 0d 20 20 20 20 |rest fra|g)).    |
|00000de0| 20 20 20 63 6f 64 65 29 | 29 0d 20 20 20 20 28 73 |   code)|).    (s|
|00000df0| 65 74 66 20 63 6f 64 65 | 20 28 6e 72 65 76 65 72 |etf code| (nrever|
|00000e00| 73 65 20 63 6f 64 65 29 | 29 0d 20 20 20 20 28 70 |se code)|).    (p|
|00000e10| 75 73 68 20 27 63 6f 6e | 64 20 63 6f 64 65 29 0d |ush 'con|d code).|
|00000e20| 20 20 20 20 28 73 65 74 | 66 20 63 6f 64 65 20 28 |    (set|f code (|
|00000e30| 6c 69 73 74 20 63 6f 64 | 65 29 29 0d 20 20 20 20 |list cod|e)).    |
|00000e40| 28 70 75 73 68 20 60 28 | 28 2c 76 61 72 20 2c 65 |(push `(|(,var ,e|
|00000e50| 78 70 29 29 20 63 6f 64 | 65 29 0d 20 20 20 20 28 |xp)) cod|e).    (|
|00000e60| 70 75 73 68 20 27 6c 65 | 74 20 63 6f 64 65 29 0d |push 'le|t code).|
|00000e70| 20 20 20 20 60 2c 63 6f | 64 65 29 29 0d 0d 28 64 |    `,co|de))..(d|
|00000e80| 65 66 6d 61 63 72 6f 20 | 61 64 64 2d 74 75 72 6e |efmacro |add-turn|
|00000e90| 20 28 6e 65 77 2d 6e 6f | 64 65 20 6e 6f 64 65 20 | (new-no|de node |
|00000ea0| 74 65 6d 70 20 70 61 74 | 68 20 64 69 72 29 0d 20 |temp pat|h dir). |
|00000eb0| 20 60 28 70 72 6f 67 6e | 0d 20 20 20 20 20 28 69 | `(progn|.     (i|
|00000ec0| 66 20 28 3d 20 2c 64 69 | 72 20 2a 72 69 67 68 74 |f (= ,di|r *right|
|00000ed0| 2a 29 0d 20 20 20 20 20 | 20 20 28 73 65 74 66 20 |*).     |  (setf |
|00000ee0| 28 62 74 72 65 65 2d 72 | 69 67 68 74 20 2c 6e 6f |(btree-r|ight ,no|
|00000ef0| 64 65 29 20 2c 6e 65 77 | 2d 6e 6f 64 65 29 0d 20 |de) ,new|-node). |
|00000f00| 20 20 20 20 20 20 28 73 | 65 74 66 20 28 62 74 72 |      (s|etf (btr|
|00000f10| 65 65 2d 6c 65 66 74 20 | 2c 6e 6f 64 65 29 20 2c |ee-left |,node) ,|
|00000f20| 6e 65 77 2d 6e 6f 64 65 | 29 29 0d 20 20 20 20 20 |new-node|)).     |
|00000f30| 28 73 65 74 66 20 28 62 | 74 72 61 69 6c 2d 64 69 |(setf (b|trail-di|
|00000f40| 72 20 2c 74 65 6d 70 29 | 20 2c 64 69 72 29 0d 20 |r ,temp)| ,dir). |
|00000f50| 20 20 20 20 28 66 6f 75 | 6e 64 2d 6e 6f 64 65 20 |    (fou|nd-node |
|00000f60| 2c 6e 65 77 2d 6e 6f 64 | 65 20 2c 70 61 74 68 29 |,new-nod|e ,path)|
|00000f70| 29 29 0d 0d 23 7c 0d 3b | 3b 20 65 78 61 6d 70 6c |))..#|.;|; exampl|
|00000f80| 65 0d 28 64 65 66 76 61 | 72 20 66 72 75 69 74 20 |e.(defva|r fruit |
|00000f90| 27 61 70 70 6c 65 29 0d | 28 73 65 6c 65 63 74 20 |'apple).|(select |
|00000fa0| 66 72 75 69 74 0d 20 20 | 20 20 20 20 20 20 28 27 |fruit.  |      ('|
|00000fb0| 61 70 70 6c 65 20 27 64 | 6f 63 74 6f 72 29 0d 20 |apple 'd|octor). |
|00000fc0| 20 20 20 20 20 20 20 28 | 27 70 65 61 63 68 20 27 |       (|'peach '|
|00000fd0| 6c 6f 76 65 72 29 0d 20 | 20 20 20 20 20 20 20 28 |lover). |       (|
|00000fe0| 6f 74 68 65 72 77 69 73 | 65 20 6e 69 6c 29 29 0d |otherwis|e nil)).|
|00000ff0| 3b 3b 20 70 72 69 6e 74 | 73 20 64 6f 63 74 6f 72 |;; print|s doctor|
|00001000| 0d 7c 23 0d 0d 3b 3b 20 | 4d 61 63 72 6f 20 77 68 |.|#..;; |Macro wh|
|00001010| 69 63 68 20 70 65 72 66 | 6f 72 6d 73 20 6f 70 65 |ich perf|orms ope|
|00001020| 72 61 74 69 6f 6e 73 20 | 6f 6e 20 61 20 62 74 72 |rations |on a btr|
|00001030| 65 65 2c 20 73 74 61 72 | 74 69 6e 67 20 61 74 20 |ee, star|ting at |
|00001040| 74 68 65 20 72 6f 6f 74 | 2e 0d 3b 3b 0d 3b 3b 20 |the root|..;;.;; |
|00001050| 57 68 65 6e 20 74 68 65 | 20 72 6f 6f 74 20 69 73 |When the| root is|
|00001060| 20 65 6d 70 74 79 3a 0d | 3b 3b 20 20 20 20 31 2e | empty:.|;;    1.|
|00001070| 20 45 78 65 63 75 74 65 | 73 20 74 68 65 20 6e 75 | Execute|s the nu|
|00001080| 6c 6c 2d 61 63 74 69 6f | 6e 0d 3b 3b 20 4f 74 68 |ll-actio|n.;; Oth|
|00001090| 65 72 77 69 73 65 20 74 | 68 72 65 61 64 73 20 74 |erwise t|hreads t|
|000010a0| 68 72 6f 75 67 68 20 74 | 68 65 20 74 72 65 65 20 |hrough t|he tree |
|000010b0| 66 72 6f 6d 20 74 6f 70 | 20 74 6f 20 62 6f 74 74 |from top| to bott|
|000010c0| 6f 6d 20 61 6e 64 20 6c | 65 66 74 20 74 6f 20 72 |om and l|eft to r|
|000010d0| 69 67 68 74 2c 0d 3b 3b | 20 61 70 70 6c 79 69 6e |ight,.;;| applyin|
|000010e0| 67 20 74 68 65 20 66 6f | 6c 6c 6f 77 69 6e 67 20 |g the fo|llowing |
|000010f0| 61 63 74 69 6f 6e 73 3a | 0d 3b 3b 20 20 20 20 31 |actions:|.;;    1|
|00001100| 2e 20 41 70 70 6c 69 65 | 73 20 74 68 65 20 6e 6f |. Applie|s the no|
|00001110| 64 65 2d 61 63 74 69 6f | 6e 20 74 6f 20 74 68 65 |de-actio|n to the|
|00001120| 20 74 72 65 65 20 0d 3b | 3b 20 20 20 20 32 2e 20 | tree .;|;    2. |
|00001130| 42 69 6e 64 73 20 74 68 | 65 20 6e 6f 64 65 20 74 |Binds th|e node t|
|00001140| 6f 20 74 68 65 20 6c 65 | 66 74 20 62 72 61 6e 63 |o the le|ft branc|
|00001150| 68 20 61 6e 64 20 62 69 | 6e 64 73 20 74 68 65 20 |h and bi|nds the |
|00001160| 6c 65 66 74 20 70 6f 73 | 69 74 69 6f 6e 61 6c 20 |left pos|itional |
|00001170| 70 61 72 61 6d 65 74 65 | 72 20 74 6f 20 74 68 65 |paramete|r to the|
|00001180| 20 6e 6f 64 65 2e 20 0d | 3b 3b 20 20 20 20 20 20 | node. .|;;      |
|00001190| 20 57 68 65 6e 20 74 68 | 65 20 6c 65 66 74 20 62 | When th|e left b|
|000011a0| 72 61 6e 63 68 20 69 73 | 20 6e 6f 74 20 65 6d 70 |ranch is| not emp|
|000011b0| 74 79 2c 20 65 76 61 6c | 75 61 74 65 73 20 74 68 |ty, eval|uates th|
|000011c0| 65 20 65 78 70 72 65 73 | 73 69 6f 6e 0d 3b 3b 20 |e expres|sion.;; |
|000011d0| 20 20 20 20 20 20 63 6f | 72 72 65 73 70 6f 6e 64 |      co|rrespond|
|000011e0| 69 6e 67 20 74 6f 20 74 | 68 65 20 62 72 61 6e 63 |ing to t|he branc|
|000011f0| 68 20 61 63 74 69 6f 6e | 2e 0d 3b 3b 20 20 20 20 |h action|..;;    |
|00001200| 32 2e 20 42 69 6e 64 73 | 20 74 68 65 20 6e 6f 64 |2. Binds| the nod|
|00001210| 65 20 74 6f 20 74 68 65 | 20 72 69 67 68 74 20 62 |e to the| right b|
|00001220| 72 61 6e 63 68 20 61 6e | 64 20 62 69 6e 64 73 20 |ranch an|d binds |
|00001230| 74 68 65 20 6c 65 66 74 | 20 70 6f 73 69 74 69 6f |the left| positio|
|00001240| 6e 61 6c 20 70 61 72 61 | 6d 65 74 65 72 20 74 6f |nal para|meter to|
|00001250| 20 74 68 65 20 6e 6f 64 | 65 2e 20 0d 3b 3b 20 20 | the nod|e. .;;  |
|00001260| 20 20 20 20 20 57 68 65 | 6e 20 74 68 65 20 6c 65 |     Whe|n the le|
|00001270| 66 74 20 62 72 61 6e 63 | 68 20 69 73 20 6e 6f 74 |ft branc|h is not|
|00001280| 20 65 6d 70 74 79 2c 20 | 65 76 61 6c 75 61 74 65 | empty, |evaluate|
|00001290| 73 20 74 68 65 20 65 78 | 70 72 65 73 73 69 6f 6e |s the ex|pression|
|000012a0| 0d 3b 3b 20 20 20 20 20 | 20 20 63 6f 72 72 65 73 |.;;     |  corres|
|000012b0| 70 6f 6e 64 69 6e 67 20 | 74 6f 20 74 68 65 20 62 |ponding |to the b|
|000012c0| 72 61 6e 63 68 20 61 63 | 74 69 6f 6e 2e 0d 3b 3b |ranch ac|tion..;;|
|000012d0| 20 20 20 20 34 2e 20 45 | 76 61 6c 75 61 74 65 73 |    4. E|valuates|
|000012e0| 20 61 6e 64 20 72 65 74 | 75 72 6e 73 20 74 68 65 | and ret|urns the|
|000012f0| 20 72 65 74 75 72 6e 20 | 65 78 70 72 65 73 73 69 | return |expressi|
|00001300| 6f 6e 2e 0d 3b 3b 20 20 | 20 20 0d 28 64 65 66 6d |on..;;  |  .(defm|
|00001310| 61 63 72 6f 20 6f 70 65 | 72 61 74 65 2d 6f 6e 2d |acro ope|rate-on-|
|00001320| 74 72 65 65 20 28 28 6e | 6f 64 65 20 74 72 65 65 |tree ((n|ode tree|
|00001330| 20 26 6f 70 74 69 6f 6e | 61 6c 20 28 6c 65 66 74 | &option|al (left|
|00001340| 20 28 67 65 6e 73 79 6d | 29 29 20 28 72 69 67 68 | (gensym|)) (righ|
|00001350| 74 20 28 67 65 6e 73 79 | 6d 29 29 29 20 26 6b 65 |t (gensy|m))) &ke|
|00001360| 79 0d 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |y.      |        |
|00001370| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 28 72 65 |        |     (re|
|00001380| 74 75 72 6e 20 6e 69 6c | 29 0d 20 20 20 20 20 20 |turn nil|).      |
|00001390| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000013a0| 20 20 20 20 20 6e 75 6c | 6c 2d 61 63 74 69 6f 6e |     nul|l-action|
|000013b0| 0d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.       |        |
|000013c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 6e 6f 64 65 |        |    node|
|000013d0| 2d 61 63 74 69 6f 6e 20 | 0d 20 20 20 20 20 20 20 |-action |.       |
|000013e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000013f0| 20 20 20 20 62 72 61 6e | 63 68 2d 61 63 74 69 6f |    bran|ch-actio|
|00001400| 6e 29 0d 20 20 60 28 6c | 65 74 20 28 2c 6e 6f 64 |n).  `(l|et (,nod|
|00001410| 65 20 2c 6c 65 66 74 20 | 2c 72 69 67 68 74 29 0d |e ,left |,right).|
|00001420| 20 20 20 20 20 28 64 65 | 63 6c 61 72 65 20 28 69 |     (de|clare (i|
|00001430| 67 6e 6f 72 61 62 6c 65 | 20 2c 6c 65 66 74 20 2c |gnorable| ,left ,|
|00001440| 72 69 67 68 74 29 29 0d | 20 20 20 20 20 28 69 66 |right)).|     (if|
|00001450| 20 28 6e 75 6c 6c 20 2c | 74 72 65 65 29 0d 20 20 | (null ,|tree).  |
|00001460| 20 20 20 20 20 2c 6e 75 | 6c 6c 2d 61 63 74 69 6f |     ,nu|ll-actio|
|00001470| 6e 0d 20 20 20 20 20 20 | 20 28 70 72 6f 67 6e 0d |n.      | (progn.|
|00001480| 20 20 20 20 20 20 20 20 | 20 2c 6e 6f 64 65 2d 61 |        | ,node-a|
|00001490| 63 74 69 6f 6e 0d 20 20 | 20 20 20 20 20 20 20 28 |ction.  |       (|
|000014a0| 77 68 65 6e 20 28 73 65 | 74 71 20 2c 6e 6f 64 65 |when (se|tq ,node|
|000014b0| 20 28 62 74 72 65 65 2d | 6c 65 66 74 20 2c 74 72 | (btree-|left ,tr|
|000014c0| 65 65 29 0d 20 20 20 20 | 20 20 20 20 20 20 20 20 |ee).    |        |
|000014d0| 20 20 20 20 20 20 20 20 | 20 2c 6c 65 66 74 20 2c |        | ,left ,|
|000014e0| 6e 6f 64 65 29 0d 20 20 | 20 20 20 20 20 20 20 20 |node).  |        |
|000014f0| 20 2c 62 72 61 6e 63 68 | 2d 61 63 74 69 6f 6e 29 | ,branch|-action)|
|00001500| 0d 20 20 20 20 20 20 20 | 20 20 28 77 68 65 6e 20 |.       |  (when |
|00001510| 28 73 65 74 71 20 2c 6e | 6f 64 65 20 28 62 74 72 |(setq ,n|ode (btr|
|00001520| 65 65 2d 72 69 67 68 74 | 20 2c 74 72 65 65 29 0d |ee-right| ,tree).|
|00001530| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001540| 20 20 20 20 20 2c 72 69 | 67 68 74 20 2c 6e 6f 64 |     ,ri|ght ,nod|
|00001550| 65 29 0d 20 20 20 20 20 | 20 20 20 20 20 20 2c 62 |e).     |      ,b|
|00001560| 72 61 6e 63 68 2d 61 63 | 74 69 6f 6e 29 0d 20 20 |ranch-ac|tion).  |
|00001570| 20 20 20 20 20 20 20 2c | 72 65 74 75 72 6e 29 29 |       ,|return))|
|00001580| 29 29 0d 0d 23 7c 20 0d | 3b 3b 20 42 61 73 69 63 |))..#| .|;; Basic|
|00001590| 20 65 78 61 6d 70 6c 65 | 3a 20 76 69 73 69 74 73 | example|: visits|
|000015a0| 20 65 76 65 72 79 20 6e | 6f 64 65 20 61 6e 64 20 | every n|ode and |
|000015b0| 64 6f 65 73 20 6e 6f 74 | 68 69 6e 67 2c 20 72 65 |does not|hing, re|
|000015c0| 74 75 72 6e 69 6e 67 20 | 74 68 65 20 74 72 65 65 |turning |the tree|
|000015d0| 0d 28 64 65 66 75 6e 20 | 77 61 6c 6b 2d 74 72 65 |.(defun |walk-tre|
|000015e0| 65 20 28 74 72 65 65 29 | 0d 20 20 28 6f 70 65 72 |e (tree)|.  (oper|
|000015f0| 61 74 65 2d 6f 6e 2d 74 | 72 65 65 20 28 6e 6f 64 |ate-on-t|ree (nod|
|00001600| 65 20 74 72 65 65 29 0d | 20 20 20 20 20 20 20 20 |e tree).|        |
|00001610| 20 20 20 20 20 20 20 20 | 20 20 20 3a 72 65 74 75 |        |   :retu|
|00001620| 72 6e 20 74 72 65 65 29 | 29 0d 0d 3b 3b 20 50 72 |rn tree)|)..;; Pr|
|00001630| 69 6e 74 73 20 61 6c 6c | 20 6e 6f 64 65 73 20 69 |ints all| nodes i|
|00001640| 6e 20 61 20 70 61 74 68 | 20 73 74 61 72 74 69 6e |n a path| startin|
|00001650| 67 20 66 72 6f 6d 20 74 | 68 65 20 72 6f 6f 74 2c |g from t|he root,|
|00001660| 20 0d 3b 3b 20 63 6f 6d | 70 6f 73 65 64 20 6f 66 | .;; com|posed of|
|00001670| 20 61 6c 74 65 72 6e 61 | 74 69 6e 67 20 6c 65 66 | alterna|ting lef|
|00001680| 74 20 61 6e 64 20 72 69 | 67 68 74 20 74 75 72 6e |t and ri|ght turn|
|00001690| 73 2c 0d 28 64 65 66 75 | 6e 20 70 72 69 6e 74 2d |s,.(defu|n print-|
|000016a0| 74 75 72 6e 20 28 74 72 | 65 65 20 26 6f 70 74 69 |turn (tr|ee &opti|
|000016b0| 6f 6e 61 6c 20 28 64 69 | 72 20 2a 6c 65 66 74 2a |onal (di|r *left*|
|000016c0| 29 29 0d 20 20 28 6f 70 | 65 72 61 74 65 2d 6f 6e |)).  (op|erate-on|
|000016d0| 2d 74 72 65 65 20 28 6e | 6f 64 65 20 74 72 65 65 |-tree (n|ode tree|
|000016e0| 20 6c 65 66 74 20 72 69 | 67 68 74 29 0d 20 20 20 | left ri|ght).   |
|000016f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001700| 3a 6e 6f 64 65 2d 61 63 | 74 69 6f 6e 20 28 70 72 |:node-ac|tion (pr|
|00001710| 69 6e 74 20 28 62 74 72 | 65 65 2d 6b 65 79 20 74 |int (btr|ee-key t|
|00001720| 72 65 65 29 29 0d 20 20 | 20 20 20 20 20 20 20 20 |ree)).  |        |
|00001730| 20 20 20 20 20 20 20 20 | 20 3a 62 72 61 6e 63 68 |        | :branch|
|00001740| 2d 61 63 74 69 6f 6e 20 | 28 69 66 20 28 65 71 75 |-action |(if (equ|
|00001750| 61 6c 20 64 69 72 20 2a | 6c 65 66 74 2a 29 0d 20 |al dir *|left*). |
|00001760| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001770| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001780| 20 20 20 28 77 68 65 6e | 20 28 65 71 20 6e 6f 64 |   (when| (eq nod|
|00001790| 65 20 6c 65 66 74 29 20 | 28 70 72 69 6e 74 2d 74 |e left) |(print-t|
|000017a0| 75 72 6e 20 6e 6f 64 65 | 20 2a 72 69 67 68 74 2a |urn node| *right*|
|000017b0| 29 29 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |)).     |        |
|000017c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000017d0| 20 20 20 20 20 20 20 28 | 77 68 65 6e 20 28 65 71 |       (|when (eq|
|000017e0| 20 6e 6f 64 65 20 72 69 | 67 68 74 29 20 28 70 72 | node ri|ght) (pr|
|000017f0| 69 6e 74 2d 74 75 72 6e | 20 6e 6f 64 65 20 2a 6c |int-turn| node *l|
|00001800| 65 66 74 2a 29 29 29 29 | 29 0d 0d 3b 3b 20 52 65 |eft*))))|)..;; Re|
|00001810| 74 75 72 6e 73 20 61 20 | 73 6f 72 74 65 64 20 6c |turns a |sorted l|
|00001820| 69 73 74 20 6f 66 20 74 | 68 65 20 6b 65 79 73 20 |ist of t|he keys |
|00001830| 6f 66 20 61 20 62 74 72 | 65 65 20 69 6e 20 64 65 |of a btr|ee in de|
|00001840| 73 63 65 6e 64 69 6e 67 | 20 6f 72 64 65 72 0d 28 |scending| order.(|
|00001850| 64 65 66 75 6e 20 70 72 | 69 6e 74 2d 6b 65 79 20 |defun pr|int-key |
|00001860| 28 74 72 65 65 20 26 6f | 70 74 69 6f 6e 61 6c 20 |(tree &o|ptional |
|00001870| 76 61 6c 75 65 73 29 0d | 20 20 28 6c 65 74 20 28 |values).|  (let (|
|00001880| 70 72 69 6e 74 2d 6e 6f | 64 65 29 0d 20 20 20 20 |print-no|de).    |
|00001890| 28 6f 70 65 72 61 74 65 | 2d 6f 6e 2d 74 72 65 65 |(operate|-on-tree|
|000018a0| 20 28 6e 6f 64 65 20 74 | 72 65 65 20 6c 65 66 74 | (node t|ree left|
|000018b0| 20 72 69 67 68 74 29 20 | 0d 20 20 20 20 20 20 20 | right) |.       |
|000018c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 3a 6e |        |      :n|
|000018d0| 6f 64 65 2d 61 63 74 69 | 6f 6e 20 28 73 65 74 71 |ode-acti|on (setq|
|000018e0| 20 70 72 69 6e 74 2d 6e | 6f 64 65 20 74 29 0d 20 | print-n|ode t). |
|000018f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001900| 20 20 20 20 3a 62 72 61 | 6e 63 68 2d 61 63 74 69 |    :bra|nch-acti|
|00001910| 6f 6e 20 28 69 66 20 28 | 65 71 20 6e 6f 64 65 20 |on (if (|eq node |
|00001920| 6c 65 66 74 29 0d 20 20 | 20 20 20 20 20 20 20 20 |left).  |        |
|00001930| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001940| 20 20 20 20 20 20 20 20 | 20 20 20 20 28 73 65 74 |        |    (set|
|00001950| 71 20 76 61 6c 75 65 73 | 20 28 70 72 69 6e 74 2d |q values| (print-|
|00001960| 6b 65 79 20 6e 6f 64 65 | 20 76 61 6c 75 65 73 29 |key node| values)|
|00001970| 29 0d 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |).      |        |
|00001980| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001990| 20 20 20 20 20 20 20 20 | 28 70 72 6f 67 6e 20 28 |        |(progn (|
|000019a0| 70 75 73 68 20 28 62 74 | 72 65 65 2d 6b 65 79 20 |push (bt|ree-key |
|000019b0| 74 72 65 65 29 20 76 61 | 6c 75 65 73 29 0d 20 20 |tree) va|lues).  |
|000019c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000019d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000019e0| 20 20 20 20 20 20 20 20 | 20 20 20 28 73 65 74 71 |        |   (setq|
|000019f0| 20 76 61 6c 75 65 73 20 | 28 70 72 69 6e 74 2d 6b | values |(print-k|
|00001a00| 65 79 20 6e 6f 64 65 20 | 76 61 6c 75 65 73 29 29 |ey node |values))|
|00001a10| 0d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.       |        |
|00001a20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001a30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 28 73 |        |      (s|
|00001a40| 65 74 71 20 70 72 69 6e | 74 2d 6e 6f 64 65 20 6e |etq prin|t-node n|
|00001a50| 69 6c 29 29 29 0d 20 20 | 20 20 20 20 20 20 20 20 |il))).  |        |
|00001a60| 20 20 20 20 20 20 20 20 | 20 20 20 3a 72 65 74 75 |        |   :retu|
|00001a70| 72 6e 20 28 70 72 6f 67 | 6e 20 0d 20 20 20 20 20 |rn (prog|n .     |
|00001a80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001a90| 20 20 20 20 20 20 20 20 | 20 20 28 77 68 65 6e 20 |        |  (when |
|00001aa0| 0d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.       |        |
|00001ab0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001ac0| 20 20 70 72 69 6e 74 2d | 6e 6f 64 65 20 28 70 75 |  print-|node (pu|
|00001ad0| 73 68 20 28 62 74 72 65 | 65 2d 6b 65 79 20 74 72 |sh (btre|e-key tr|
|00001ae0| 65 65 29 20 76 61 6c 75 | 65 73 29 29 0d 20 20 20 |ee) valu|es)).   |
|00001af0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001b00| 20 20 20 20 20 20 20 20 | 20 20 20 20 76 61 6c 75 |        |    valu|
|00001b10| 65 73 29 29 29 29 0d 7c | 23 0d 0d 3b 3b 20 62 61 |es)))).||#..;; ba|
|00001b20| 73 69 63 20 63 6f 70 79 | 20 66 75 6e 63 74 69 6f |sic copy| functio|
|00001b30| 6e 0d 0d 28 64 65 66 75 | 6e 20 2a 63 6f 70 79 2d |n..(defu|n *copy-|
|00001b40| 62 74 72 65 65 20 28 75 | 20 26 6f 70 74 69 6f 6e |btree (u| &option|
|00001b50| 61 6c 20 28 64 65 73 63 | 65 6e 64 20 30 29 29 0d |al (desc|end 0)).|
|00001b60| 20 20 22 43 72 65 61 74 | 65 20 61 20 63 6f 70 79 |  "Creat|e a copy|
|00001b70| 20 6f 66 20 61 20 62 74 | 72 65 65 20 75 73 69 6e | of a bt|ree usin|
|00001b80| 67 20 74 68 65 20 69 6e | 74 65 67 65 72 20 64 65 |g the in|teger de|
|00001b90| 73 63 65 6e 64 20 74 6f | 20 63 6f 6e 74 72 6f 6c |scend to| control|
|00001ba0| 20 68 6f 77 0d 74 6f 20 | 63 6f 70 79 20 74 68 65 | how.to |copy the|
|00001bb0| 20 76 61 6c 75 65 73 2e | 0d 43 6f 70 79 20 74 68 | values.|.Copy th|
|00001bc0| 65 20 6b 65 79 73 20 75 | 73 69 6e 67 20 63 6f 70 |e keys u|sing cop|
|00001bd0| 79 2d 74 72 65 65 2e 0d | 43 6f 70 79 20 74 68 65 |y-tree..|Copy the|
|00001be0| 20 76 61 6c 75 65 73 20 | 69 6e 20 6f 6e 65 20 6f | values |in one o|
|00001bf0| 66 20 74 77 6f 20 77 61 | 79 73 3a 0d 20 20 20 49 |f two wa|ys:.   I|
|00001c00| 66 20 64 65 73 63 65 6e | 64 20 3e 20 30 2c 20 64 |f descen|d > 0, d|
|00001c10| 65 63 72 65 6d 65 6e 74 | 20 64 65 73 63 65 6e 64 |ecrement| descend|
|00001c20| 20 61 6e 64 0d 20 20 20 | 20 20 63 6f 70 79 20 74 | and.   |  copy t|
|00001c30| 68 65 20 62 74 72 65 65 | 73 20 63 6f 72 72 65 73 |he btree|s corres|
|00001c40| 70 6f 6e 64 69 6e 67 20 | 74 6f 20 74 68 65 20 6e |ponding |to the n|
|00001c50| 6f 64 65 20 76 61 6c 75 | 65 73 2e 0d 20 20 20 4f |ode valu|es..   O|
|00001c60| 74 68 65 72 77 69 73 65 | 20 75 73 65 20 63 6f 70 |therwise| use cop|
|00001c70| 79 2d 74 72 65 65 20 74 | 6f 20 63 6f 70 79 20 74 |y-tree t|o copy t|
|00001c80| 68 65 20 76 61 6c 75 65 | 73 22 0d 20 20 28 6c 65 |he value|s".  (le|
|00001c90| 74 2a 20 28 28 76 61 6c | 20 28 69 66 20 28 3e 20 |t* ((val| (if (> |
|00001ca0| 64 65 73 63 65 6e 64 20 | 30 29 0d 20 20 20 20 20 |descend |0).     |
|00001cb0| 20 20 20 20 20 20 20 20 | 20 20 20 28 2a 63 6f 70 |        |   (*cop|
|00001cc0| 79 2d 62 74 72 65 65 20 | 28 62 74 72 65 65 2d 76 |y-btree |(btree-v|
|00001cd0| 61 6c 20 75 29 20 28 31 | 2d 20 64 65 73 63 65 6e |al u) (1|- descen|
|00001ce0| 64 29 29 0d 20 20 20 20 | 20 20 20 20 20 20 20 20 |d)).    |        |
|00001cf0| 20 20 20 20 28 63 6f 70 | 79 2d 74 72 65 65 20 28 |    (cop|y-tree (|
|00001d00| 62 74 72 65 65 2d 76 61 | 6c 20 75 29 29 29 29 0d |btree-va|l u)))).|
|00001d10| 20 20 20 20 20 20 20 20 | 20 6e 65 77 2d 6e 6f 64 |        | new-nod|
|00001d20| 65 20 0d 20 20 20 20 20 | 20 20 20 20 6d 69 6e 0d |e .     |    min.|
|00001d30| 20 20 20 20 20 20 20 20 | 20 6d 61 78 29 0d 20 20 |        | max).  |
|00001d40| 20 20 28 6f 70 65 72 61 | 74 65 2d 6f 6e 2d 74 72 |  (opera|te-on-tr|
|00001d50| 65 65 20 28 6e 6f 64 65 | 20 75 20 6c 65 66 74 20 |ee (node| u left |
|00001d60| 72 69 67 68 74 29 0d 20 | 20 20 20 20 20 20 20 20 |right). |        |
|00001d70| 20 20 20 20 20 20 20 20 | 20 20 20 20 3a 6e 6f 64 |        |    :nod|
|00001d80| 65 2d 61 63 74 69 6f 6e | 20 28 73 65 74 71 20 6e |e-action| (setq n|
|00001d90| 65 77 2d 6e 6f 64 65 20 | 28 6d 61 6b 65 2d 62 74 |ew-node |(make-bt|
|00001da0| 72 65 65 20 3a 6b 65 79 | 20 28 63 6f 70 79 2d 74 |ree :key| (copy-t|
|00001db0| 72 65 65 20 28 62 74 72 | 65 65 2d 6b 65 79 20 75 |ree (btr|ee-key u|
|00001dc0| 29 29 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |)).     |        |
|00001dd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001de0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001df0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001e00| 3a 76 61 6c 20 76 61 6c | 0d 20 20 20 20 20 20 20 |:val val|.       |
|00001e10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001e20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001e30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001e40| 20 20 20 20 20 20 3a 62 | 61 6c 61 6e 63 65 20 28 |      :b|alance (|
|00001e50| 62 74 72 65 65 2d 62 61 | 6c 61 6e 63 65 20 75 29 |btree-ba|lance u)|
|00001e60| 29 29 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |)).     |        |
|00001e70| 20 20 20 20 20 20 20 20 | 3a 62 72 61 6e 63 68 2d |        |:branch-|
|00001e80| 61 63 74 69 6f 6e 20 28 | 2a 63 6f 70 79 2d 62 74 |action (|*copy-bt|
|00001e90| 72 65 65 20 6e 6f 64 65 | 20 64 65 73 63 65 6e 64 |ree node| descend|
|00001ea0| 29 0d 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |).      |        |
|00001eb0| 20 20 20 20 20 20 20 3a | 72 65 74 75 72 6e 20 28 |       :|return (|
|00001ec0| 70 72 6f 67 6e 0d 20 20 | 20 20 20 20 20 20 20 20 |progn.  |        |
|00001ed0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001ee0| 20 20 20 20 20 28 73 65 | 74 71 20 6d 69 6e 20 28 |     (se|tq min (|
|00001ef0| 6f 72 20 28 62 74 72 65 | 65 2d 6d 69 6e 20 6c 65 |or (btre|e-min le|
|00001f00| 66 74 29 20 6c 65 66 74 | 29 0d 20 20 20 20 20 20 |ft) left|).      |
|00001f10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001f20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 6d |        |       m|
|00001f30| 61 78 20 28 6f 72 20 28 | 62 74 72 65 65 2d 6d 61 |ax (or (|btree-ma|
|00001f40| 78 20 72 69 67 68 74 29 | 20 72 69 67 68 74 29 29 |x right)| right))|
|00001f50| 0d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.       |        |
|00001f60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001f70| 28 73 65 74 66 20 28 62 | 74 72 65 65 2d 6d 69 6e |(setf (b|tree-min|
|00001f80| 20 6e 65 77 2d 6e 6f 64 | 65 29 20 6d 69 6e 0d 20 | new-nod|e) min. |
|00001f90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001fa0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001fb0| 20 20 20 20 28 62 74 72 | 65 65 2d 6d 61 78 20 6e |    (btr|ee-max n|
|00001fc0| 65 77 2d 6e 6f 64 65 29 | 20 6d 61 78 0d 20 20 20 |ew-node)| max.   |
|00001fd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001fe0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001ff0| 20 20 28 62 74 72 65 65 | 2d 72 69 67 68 74 20 6e |  (btree|-right n|
|00002000| 65 77 2d 6e 6f 64 65 29 | 20 72 69 67 68 74 0d 20 |ew-node)| right. |
|00002010| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00002020| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00002030| 20 20 20 20 28 62 74 72 | 65 65 2d 6c 65 66 74 20 |    (btr|ee-left |
|00002040| 6e 65 77 2d 6e 6f 64 65 | 29 20 6c 65 66 74 29 0d |new-node|) left).|
|00002050| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00002060| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 6e |        |       n|
|00002070| 65 77 2d 6e 6f 64 65 29 | 29 29 29 0d 0d 3b 3b 20 |ew-node)|)))..;; |
|00002080| 62 61 73 69 63 20 63 6f | 6d 70 61 72 69 73 6f 6e |basic co|mparison|
|00002090| 20 66 75 6e 63 74 69 6f | 6e 73 0d 28 64 65 66 75 | functio|ns.(defu|
|000020a0| 6e 20 63 6f 6d 70 61 72 | 65 20 28 6d 20 6e 29 0d |n compar|e (m n).|
|000020b0| 20 20 3b 3b 20 66 6f 72 | 20 69 6e 74 65 67 65 72 |  ;; for| integer|
|000020c0| 73 20 6d 20 61 6e 64 20 | 6e 2c 20 62 65 68 61 76 |s m and |n, behav|
|000020d0| 65 73 20 6c 69 6b 65 20 | 61 20 66 6f 72 74 72 61 |es like |a fortra|
|000020e0| 6e 20 63 6f 6d 70 75 74 | 65 64 20 69 66 0d 20 20 |n comput|ed if.  |
|000020f0| 28 63 6f 6e 64 20 28 28 | 3d 20 6d 20 6e 29 20 2a |(cond ((|= m n) *|
|00002100| 65 71 75 61 6c 2a 29 0d | 20 20 20 20 20 20 20 20 |equal*).|        |
|00002110| 28 28 3c 20 6d 20 6e 29 | 20 2a 62 65 66 6f 72 65 |((< m n)| *before|
|00002120| 2a 29 0d 20 20 20 20 20 | 20 20 20 28 74 20 2a 61 |*).     |   (t *a|
|00002130| 66 74 65 72 2a 29 29 29 | 0d 0d 28 64 65 66 75 6e |fter*)))|..(defun|
|00002140| 20 69 73 2d 6c 65 73 73 | 20 28 61 20 62 20 74 68 | is-less| (a b th|
|00002150| 65 2d 70 72 65 64 29 0d | 20 20 28 3d 20 28 66 75 |e-pred).|  (= (fu|
|00002160| 6e 63 61 6c 6c 20 74 68 | 65 2d 70 72 65 64 20 61 |ncall th|e-pred a|
|00002170| 20 62 29 20 2a 62 65 66 | 6f 72 65 2a 29 29 0d 0d | b) *bef|ore*))..|
|00002180| 3b 3b 20 62 61 73 69 63 | 20 74 72 65 65 20 66 75 |;; basic| tree fu|
|00002190| 6e 63 74 69 6f 6e 73 0d | 28 64 65 66 75 6e 20 63 |nctions.|(defun c|
|000021a0| 68 65 63 6b 2d 74 72 65 | 65 20 28 74 72 65 65 20 |heck-tre|e (tree |
|000021b0| 6d 69 6e 20 6d 61 78 29 | 0d 20 20 22 64 65 74 65 |min max)|.  "dete|
|000021c0| 72 6d 69 6e 65 73 20 77 | 68 65 74 68 65 72 20 74 |rmines w|hether t|
|000021d0| 68 65 20 74 72 65 65 20 | 69 73 20 68 65 69 67 68 |he tree |is heigh|
|000021e0| 74 20 62 61 6c 61 6e 63 | 65 64 20 61 6e 64 20 61 |t balanc|ed and a|
|000021f0| 6c 6c 20 6e 6f 64 65 73 | 20 69 6e 20 74 68 65 20 |ll nodes| in the |
|00002200| 74 72 65 65 0d 61 72 65 | 20 62 65 74 77 65 65 6e |tree.are| between|
|00002210| 20 6d 69 6e 20 61 6e 64 | 20 6d 61 78 22 0d 20 20 | min and| max".  |
|00002220| 28 61 6e 64 20 28 61 6c | 6c 2d 68 65 69 67 68 74 |(and (al|l-height|
|00002230| 2d 62 61 6c 61 6e 63 65 | 64 20 74 72 65 65 29 0d |-balance|d tree).|
|00002240| 20 20 20 20 20 20 20 28 | 63 68 65 63 6b 2d 74 72 |       (|check-tr|
|00002250| 65 65 31 20 74 72 65 65 | 20 6d 69 6e 20 6d 61 78 |ee1 tree| min max|
|00002260| 29 29 29 0d 0d 28 64 65 | 66 75 6e 20 63 68 65 63 |)))..(de|fun chec|
|00002270| 6b 2d 74 72 65 65 31 20 | 28 74 72 65 65 20 6d 69 |k-tree1 |(tree mi|
|00002280| 6e 20 6d 61 78 29 0d 20 | 20 22 64 65 74 65 72 6d |n max). | "determ|
|00002290| 69 6e 65 73 20 77 68 65 | 74 68 65 72 20 74 68 65 |ines whe|ther the|
|000022a0| 20 6e 6f 64 65 73 20 69 | 6e 20 74 68 65 20 74 72 | nodes i|n the tr|
|000022b0| 65 65 20 72 61 6e 67 65 | 20 62 65 74 77 65 65 6e |ee range| between|
|000022c0| 20 74 68 65 20 6d 69 6e | 20 61 6e 64 20 6d 61 78 | the min| and max|
|000022d0| 0d 76 61 6c 75 65 73 20 | 6f 66 20 74 68 65 20 70 |.values |of the p|
|000022e0| 61 72 65 6e 74 22 0d 20 | 20 28 6c 65 74 20 28 6e |arent". | (let (n|
|000022f0| 6f 64 65 29 0d 20 20 20 | 20 28 69 66 20 28 6e 75 |ode).   | (if (nu|
|00002300| 6c 6c 20 74 72 65 65 29 | 0d 20 20 20 20 20 20 74 |ll tree)|.      t|
|00002310| 0d 20 20 20 20 20 20 28 | 61 6e 64 0d 20 20 20 20 |.      (|and.    |
|00002320| 20 20 20 28 69 66 20 28 | 6f 72 20 28 3e 20 28 62 |   (if (|or (> (b|
|00002330| 74 72 65 65 2d 6b 65 79 | 20 74 72 65 65 29 20 6d |tree-key| tree) m|
|00002340| 61 78 29 0d 20 20 20 20 | 20 20 20 20 20 20 20 20 |ax).    |        |
|00002350| 20 20 20 28 3c 20 28 62 | 74 72 65 65 2d 6b 65 79 |   (< (b|tree-key|
|00002360| 20 74 72 65 65 29 20 6d | 69 6e 29 29 0d 20 20 20 | tree) m|in)).   |
|00002370| 20 20 20 20 20 20 28 70 | 72 6f 67 6e 0d 20 20 20 |      (p|rogn.   |
|00002380| 20 20 20 20 20 20 20 20 | 28 70 72 69 6e 74 2d 64 |        |(print-d|
|00002390| 62 20 6d 61 78 20 6d 69 | 6e 20 28 62 74 72 65 65 |b max mi|n (btree|
|000023a0| 2d 6b 65 79 20 74 72 65 | 65 29 0d 20 20 20 20 20 |-key tre|e).     |
|000023b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000023c0| 28 3e 20 28 62 74 72 65 | 65 2d 6b 65 79 20 74 72 |(> (btre|e-key tr|
|000023d0| 65 65 29 20 6d 61 78 29 | 0d 20 20 20 20 20 20 20 |ee) max)|.       |
|000023e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 28 3c |        |      (<|
|000023f0| 20 28 62 74 72 65 65 2d | 6b 65 79 20 74 72 65 65 | (btree-|key tree|
|00002400| 29 20 6d 69 6e 29 29 0d | 20 20 20 20 20 20 20 20 |) min)).|        |
|00002410| 20 20 20 28 70 72 69 6e | 74 2d 74 72 65 65 20 74 |   (prin|t-tree t|
|00002420| 72 65 65 29 0d 20 20 20 | 20 20 20 20 20 20 20 20 |ree).   |        |
|00002430| 6e 69 6c 29 0d 20 20 20 | 20 20 20 20 20 20 74 29 |nil).   |      t)|
|00002440| 0d 20 20 20 20 20 20 20 | 28 70 72 6f 67 6e 0d 20 |.       |(progn. |
|00002450| 20 20 20 20 20 20 20 20 | 28 73 65 74 71 20 6e 6f |        |(setq no|
|00002460| 64 65 20 28 62 74 72 65 | 65 2d 6c 65 66 74 20 74 |de (btre|e-left t|
|00002470| 72 65 65 29 29 0d 20 20 | 20 20 20 20 20 20 20 28 |ree)).  |       (|
|00002480| 61 6e 64 20 28 6f 72 20 | 28 6e 75 6c 6c 20 6e 6f |and (or |(null no|
|00002490| 64 65 29 0d 20 20 20 20 | 20 20 20 20 20 20 20 20 |de).    |        |
|000024a0| 20 20 20 20 20 20 28 3c | 3d 20 28 6d 69 6e 2d 76 |      (<|= (min-v|
|000024b0| 61 6c 20 6e 6f 64 65 29 | 20 28 62 74 72 65 65 2d |al node)| (btree-|
|000024c0| 6b 65 79 20 74 72 65 65 | 29 29 29 0d 20 20 20 20 |key tree|))).    |
|000024d0| 20 20 20 20 20 20 20 20 | 20 20 28 63 68 65 63 6b |        |  (check|
|000024e0| 2d 74 72 65 65 31 20 6e | 6f 64 65 20 28 6d 69 6e |-tree1 n|ode (min|
|000024f0| 2d 76 61 6c 20 6e 6f 64 | 65 29 20 28 6d 61 78 2d |-val nod|e) (max-|
|00002500| 76 61 6c 20 6e 6f 64 65 | 29 29 29 29 0d 20 20 20 |val node|)))).   |
|00002510| 20 20 20 20 28 70 72 6f | 67 6e 20 28 73 65 74 71 |    (pro|gn (setq|
|00002520| 20 6e 6f 64 65 20 28 62 | 74 72 65 65 2d 72 69 67 | node (b|tree-rig|
|00002530| 68 74 20 74 72 65 65 29 | 29 0d 20 20 20 20 20 20 |ht tree)|).      |
|00002540| 20 20 20 20 20 20 20 20 | 28 61 6e 64 20 28 6f 72 |        |(and (or|
|00002550| 20 28 6e 75 6c 6c 20 6e | 6f 64 65 29 0d 20 20 20 | (null n|ode).   |
|00002560| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00002570| 20 20 20 20 28 3e 3d 20 | 28 6d 61 78 2d 76 61 6c |    (>= |(max-val|
|00002580| 20 6e 6f 64 65 29 20 28 | 62 74 72 65 65 2d 6b 65 | node) (|btree-ke|
|00002590| 79 20 74 72 65 65 29 29 | 29 20 0d 20 20 20 20 20 |y tree))|) .     |
|000025a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 28 63 |        |      (c|
|000025b0| 68 65 63 6b 2d 74 72 65 | 65 31 20 6e 6f 64 65 20 |heck-tre|e1 node |
|000025c0| 28 6d 69 6e 2d 76 61 6c | 20 6e 6f 64 65 29 20 28 |(min-val| node) (|
|000025d0| 6d 61 78 2d 76 61 6c 20 | 6e 6f 64 65 29 29 29 29 |max-val |node))))|
|000025e0| 29 29 29 29 0d 0d 3b 3b | 20 62 74 72 65 65 20 68 |))))..;;| btree h|
|000025f0| 65 69 67 68 74 20 66 75 | 6e 63 74 69 6f 6e 73 0d |eight fu|nctions.|
|00002600| 0d 28 64 65 66 75 6e 20 | 6d 65 74 72 69 63 2d 62 |.(defun |metric-b|
|00002610| 74 72 65 65 20 28 62 74 | 72 65 65 29 0d 20 20 22 |tree (bt|ree).  "|
|00002620| 50 72 69 6e 74 20 61 20 | 63 6f 75 6e 74 20 6f 66 |Print a |count of|
|00002630| 20 74 68 65 20 6e 75 6d | 62 65 72 20 6f 66 20 6e | the num|ber of n|
|00002640| 6f 64 65 73 20 69 6e 20 | 61 20 74 72 65 65 2c 20 |odes in |a tree, |
|00002650| 74 68 65 20 6d 61 78 69 | 6d 75 6d 20 68 65 69 67 |the maxi|mum heig|
|00002660| 68 74 20 61 6e 64 20 0d | 74 68 65 20 64 65 76 69 |ht and .|the devi|
|00002670| 61 74 69 6f 6e 20 66 72 | 6f 6d 20 74 68 65 20 69 |ation fr|om the i|
|00002680| 64 65 61 6c 22 0d 20 20 | 28 6c 65 74 20 28 28 6e |deal".  |(let ((n|
|00002690| 6f 64 65 73 20 28 63 6f | 75 6e 74 2d 6e 6f 64 65 |odes (co|unt-node|
|000026a0| 73 20 62 74 72 65 65 29 | 29 0d 20 20 20 20 20 20 |s btree)|).      |
|000026b0| 20 20 28 68 65 69 67 68 | 74 20 28 68 65 69 67 68 |  (heigh|t (heigh|
|000026c0| 74 2d 62 74 72 65 65 20 | 62 74 72 65 65 29 29 29 |t-btree |btree)))|
|000026d0| 0d 20 20 20 20 28 66 6f | 72 6d 61 74 20 74 20 22 |.    (fo|rmat t "|
|000026e0| 7e 26 6e 6f 64 65 73 3d | 7e 64 20 68 65 69 67 68 |~&nodes=|~d heigh|
|000026f0| 74 3d 7e 64 20 69 64 65 | 61 6c 2f 61 63 74 75 61 |t=~d ide|al/actua|
|00002700| 6c 20 3d 20 7e 64 25 7e | 25 22 0d 20 20 20 20 20 |l = ~d%~|%".     |
|00002710| 20 20 20 20 20 20 20 6e | 6f 64 65 73 20 68 65 69 |       n|odes hei|
|00002720| 67 68 74 20 28 72 6f 75 | 6e 64 20 28 2a 20 31 30 |ght (rou|nd (* 10|
|00002730| 30 20 28 6c 6f 67 20 6e | 6f 64 65 73 20 32 29 29 |0 (log n|odes 2))|
|00002740| 20 20 68 65 69 67 68 74 | 29 0d 20 20 20 20 20 20 |  height|).      |
|00002750| 20 20 20 20 20 20 29 29 | 29 0d 0d 28 64 65 66 75 |      ))|)..(defu|
|00002760| 6e 20 68 65 69 67 68 74 | 2d 62 74 72 65 65 20 28 |n height|-btree (|
|00002770| 62 74 72 65 65 20 26 6f | 70 74 69 6f 6e 61 6c 20 |btree &o|ptional |
|00002780| 28 6e 20 30 29 29 0d 20 | 20 28 69 66 20 28 6e 75 |(n 0)). | (if (nu|
|00002790| 6c 6c 20 62 74 72 65 65 | 29 20 6e 0d 20 20 20 20 |ll btree|) n.    |
|000027a0| 20 20 28 6d 61 78 20 28 | 68 65 69 67 68 74 2d 62 |  (max (|height-b|
|000027b0| 74 72 65 65 20 28 62 74 | 72 65 65 2d 6c 65 66 74 |tree (bt|ree-left|
|000027c0| 20 62 74 72 65 65 29 20 | 28 31 2b 20 6e 29 29 0d | btree) |(1+ n)).|
|000027d0| 20 20 20 20 20 20 20 20 | 20 20 20 28 68 65 69 67 |        |   (heig|
|000027e0| 68 74 2d 62 74 72 65 65 | 20 28 62 74 72 65 65 2d |ht-btree| (btree-|
|000027f0| 72 69 67 68 74 20 62 74 | 72 65 65 29 20 28 31 2b |right bt|ree) (1+|
|00002800| 20 6e 29 29 29 29 29 0d | 0d 28 64 65 66 75 6e 20 | n))))).|.(defun |
|00002810| 63 6f 75 6e 74 2d 6e 6f | 64 65 73 20 28 62 74 72 |count-no|des (btr|
|00002820| 65 65 29 0d 20 20 28 69 | 66 20 28 6e 75 6c 6c 20 |ee).  (i|f (null |
|00002830| 62 74 72 65 65 29 20 30 | 0d 20 20 20 20 20 20 28 |btree) 0|.      (|
|00002840| 2b 20 28 31 2b 20 28 63 | 6f 75 6e 74 2d 6e 6f 64 |+ (1+ (c|ount-nod|
|00002850| 65 73 20 28 62 74 72 65 | 65 2d 6c 65 66 74 20 62 |es (btre|e-left b|
|00002860| 74 72 65 65 29 29 29 0d | 20 20 20 20 20 20 20 20 |tree))).|        |
|00002870| 20 28 63 6f 75 6e 74 2d | 6e 6f 64 65 73 20 28 62 | (count-|nodes (b|
|00002880| 74 72 65 65 2d 72 69 67 | 68 74 20 62 74 72 65 65 |tree-rig|ht btree|
|00002890| 29 29 29 29 29 0d 0d 3b | 3b 20 6c 69 6e 6b 20 72 |)))))..;|; link r|
|000028a0| 6f 75 74 69 6e 65 73 20 | 66 72 6f 6d 20 4b 6e 75 |outines |from Knu|
|000028b0| 74 68 20 0d 28 64 65 66 | 75 6e 20 6c 69 6e 6b 20 |th .(def|un link |
|000028c0| 28 64 69 72 20 6e 6f 64 | 65 29 0d 20 20 3b 3b 20 |(dir nod|e).  ;; |
|000028d0| 20 28 6c 69 6e 6b 20 2a | 72 69 67 68 74 2a 20 6e | (link *|right* n|
|000028e0| 6f 64 65 29 20 3d 20 28 | 62 74 72 65 65 2d 72 69 |ode) = (|btree-ri|
|000028f0| 67 68 74 20 6e 6f 64 65 | 29 0d 20 20 3b 3b 20 20 |ght node|).  ;;  |
|00002900| 28 6c 69 6e 6b 20 2a 6c | 65 66 74 2a 20 6e 6f 64 |(link *l|eft* nod|
|00002910| 65 29 20 20 3d 20 28 62 | 74 72 65 65 2d 6c 65 66 |e)  = (b|tree-lef|
|00002920| 74 20 6e 6f 64 65 29 0d | 20 20 28 69 66 20 28 65 |t node).|  (if (e|
|00002930| 71 75 61 6c 20 64 69 72 | 20 2a 72 69 67 68 74 2a |qual dir| *right*|
|00002940| 29 0d 20 20 20 20 28 62 | 74 72 65 65 2d 72 69 67 |).    (b|tree-rig|
|00002950| 68 74 20 6e 6f 64 65 29 | 0d 20 20 20 20 28 62 74 |ht node)|.    (bt|
|00002960| 72 65 65 2d 6c 65 66 74 | 20 6e 6f 64 65 29 29 29 |ree-left| node)))|
|00002970| 0d 0d 28 64 65 66 75 6e | 20 73 65 74 2d 6c 69 6e |..(defun| set-lin|
|00002980| 6b 20 28 64 69 72 20 6e | 6f 64 65 20 76 61 6c 75 |k (dir n|ode valu|
|00002990| 65 29 0d 20 20 3b 3b 20 | 20 28 73 65 74 2d 6c 69 |e).  ;; | (set-li|
|000029a0| 6e 6b 20 2a 72 69 67 68 | 74 2a 20 6e 6f 64 65 20 |nk *righ|t* node |
|000029b0| 76 61 6c 75 65 29 20 3d | 20 28 73 65 74 66 20 28 |value) =| (setf (|
|000029c0| 62 74 72 65 65 2d 72 69 | 67 68 74 20 6e 6f 64 65 |btree-ri|ght node|
|000029d0| 29 20 76 61 6c 75 65 29 | 0d 20 20 3b 3b 20 20 28 |) value)|.  ;;  (|
|000029e0| 73 65 74 2d 6c 69 6e 6b | 20 2a 6c 65 66 74 2a 20 |set-link| *left* |
|000029f0| 6e 6f 64 65 20 76 61 6c | 75 65 29 20 20 3d 20 28 |node val|ue)  = (|
|00002a00| 73 65 74 66 20 28 62 74 | 72 65 65 2d 6c 65 66 74 |setf (bt|ree-left|
|00002a10| 20 6e 6f 64 65 29 20 76 | 61 6c 75 65 29 0d 20 20 | node) v|alue).  |
|00002a20| 28 77 68 65 6e 20 6e 6f | 64 65 0d 20 20 20 20 28 |(when no|de.    (|
|00002a30| 69 66 20 28 65 71 75 61 | 6c 20 64 69 72 20 2a 72 |if (equa|l dir *r|
|00002a40| 69 67 68 74 2a 29 0d 20 | 20 20 20 20 20 28 73 65 |ight*). |     (se|
|00002a50| 74 66 20 28 62 74 72 65 | 65 2d 72 69 67 68 74 20 |tf (btre|e-right |
|00002a60| 6e 6f 64 65 29 20 76 61 | 6c 75 65 29 0d 20 20 20 |node) va|lue).   |
|00002a70| 20 20 20 28 73 65 74 66 | 20 28 62 74 72 65 65 2d |   (setf| (btree-|
|00002a80| 6c 65 66 74 20 6e 6f 64 | 65 29 20 76 61 6c 75 65 |left nod|e) value|
|00002a90| 29 29 29 29 0d 0d 3b 3b | 3b 20 50 72 69 6e 74 69 |))))..;;|; Printi|
|00002aa0| 6e 67 0d 3b 3b 20 20 20 | 20 20 20 20 74 72 65 65 |ng.;;   |    tree|
|00002ab0| 73 0d 28 64 65 66 75 6e | 20 62 61 6c 61 6e 63 65 |s.(defun| balance|
|00002ac0| 2d 73 74 72 69 6e 67 20 | 28 6e 6f 64 65 29 0d 20 |-string |(node). |
|00002ad0| 20 28 73 65 6c 65 63 74 | 20 28 62 74 72 65 65 2d | (select| (btree-|
|00002ae0| 62 61 6c 61 6e 63 65 20 | 6e 6f 64 65 29 0d 20 20 |balance |node).  |
|00002af0| 20 20 28 2a 72 69 67 68 | 74 2d 74 61 6c 6c 65 72 |  (*righ|t-taller|
|00002b00| 2a 20 22 52 22 29 0d 20 | 20 20 20 28 2a 6c 65 66 |* "R"). |   (*lef|
|00002b10| 74 2d 74 61 6c 6c 65 72 | 2a 20 22 4c 22 29 0d 20 |t-taller|* "L"). |
|00002b20| 20 20 20 28 2a 62 61 6c | 61 6e 63 65 64 2a 20 22 |   (*bal|anced* "|
|00002b30| 20 22 29 0d 20 20 20 20 | 28 6f 74 68 65 72 77 69 | ").    |(otherwi|
|00002b40| 73 65 20 22 3f 22 29 29 | 29 0d 0d 28 64 65 66 75 |se "?"))|)..(defu|
|00002b50| 6e 20 64 69 72 65 63 74 | 69 6f 6e 2d 73 74 72 69 |n direct|ion-stri|
|00002b60| 6e 67 20 28 64 69 72 29 | 0d 20 20 28 73 65 6c 65 |ng (dir)|.  (sele|
|00002b70| 63 74 20 64 69 72 0d 20 | 20 20 20 28 2a 72 69 67 |ct dir. |   (*rig|
|00002b80| 68 74 2a 20 22 52 22 29 | 0d 20 20 20 20 28 2a 6c |ht* "R")|.    (*l|
|00002b90| 65 66 74 2a 20 22 4c 22 | 29 0d 20 20 20 20 28 2a |eft* "L"|).    (*|
|00002ba0| 65 71 75 61 6c 2a 20 22 | 20 22 29 0d 20 20 20 20 |equal* "| ").    |
|00002bb0| 28 6f 74 68 65 72 77 69 | 73 65 20 22 2e 22 29 29 |(otherwi|se "."))|
|00002bc0| 29 0d 0d 28 64 65 66 75 | 6e 20 74 72 65 65 2d 64 |)..(defu|n tree-d|
|00002bd0| 69 72 65 63 74 69 6f 6e | 2d 73 74 72 69 6e 67 20 |irection|-string |
|00002be0| 28 64 69 72 29 0d 20 20 | 28 73 65 6c 65 63 74 20 |(dir).  |(select |
|00002bf0| 64 69 72 0d 20 20 20 20 | 28 2a 72 69 67 68 74 2a |dir.    |(*right*|
|00002c00| 20 22 4c 3a 22 29 0d 20 | 20 20 20 28 2a 6c 65 66 | "L:"). |   (*lef|
|00002c10| 74 2a 20 22 52 3a 22 29 | 0d 20 20 20 20 28 6f 74 |t* "R:")|.    (ot|
|00002c20| 68 65 72 77 69 73 65 20 | 22 3d 3a 22 29 29 29 0d |herwise |"=:"))).|
|00002c30| 0d 28 64 65 66 75 6e 20 | 70 72 69 6e 74 2d 6e 6f |.(defun |print-no|
|00002c40| 64 65 20 28 75 20 6c 65 | 76 65 6c 20 64 69 72 20 |de (u le|vel dir |
|00002c50| 26 6b 65 79 20 74 69 74 | 6c 65 29 0d 20 20 28 66 |&key tit|le).  (f|
|00002c60| 6f 72 6d 61 74 20 74 20 | 22 7e 26 7e 40 3f 7e 61 |ormat t |"~&~@?~a|
|00002c70| 20 7e 73 20 7e 61 20 5b | 7e 64 20 7e 64 5d 20 7e | ~s ~a [|~d ~d] ~|
|00002c80| 61 7e 25 22 0d 20 20 20 | 20 20 20 20 20 20 20 28 |a~%".   |       (|
|00002c90| 66 6f 72 6d 61 74 20 6e | 69 6c 20 22 7e 7e 7e 64 |format n|il "~~~d|
|00002ca0| 74 22 20 20 6c 65 76 65 | 6c 29 0d 20 20 20 20 20 |t"  leve|l).     |
|00002cb0| 20 20 20 20 20 28 62 61 | 6c 61 6e 63 65 2d 73 74 |     (ba|lance-st|
|00002cc0| 72 69 6e 67 20 75 29 0d | 20 20 20 20 20 20 20 20 |ring u).|        |
|00002cd0| 20 20 28 62 74 72 65 65 | 2d 6b 65 79 20 75 29 0d |  (btree|-key u).|
|00002ce0| 20 20 20 20 20 20 20 20 | 20 20 28 64 69 72 65 63 |        |  (direc|
|00002cf0| 74 69 6f 6e 2d 73 74 72 | 69 6e 67 20 64 69 72 29 |tion-str|ing dir)|
|00002d00| 0d 20 20 20 20 20 20 20 | 20 20 20 28 62 74 72 65 |.       |   (btre|
|00002d10| 65 2d 6b 65 79 20 28 62 | 74 72 65 65 2d 6d 69 6e |e-key (b|tree-min|
|00002d20| 20 75 29 29 0d 20 20 20 | 20 20 20 20 20 20 20 28 | u)).   |       (|
|00002d30| 62 74 72 65 65 2d 6b 65 | 79 20 28 62 74 72 65 65 |btree-ke|y (btree|
|00002d40| 2d 6d 61 78 20 75 29 29 | 0d 20 20 20 20 20 20 20 |-max u))|.       |
|00002d50| 20 20 20 28 69 66 20 74 | 69 74 6c 65 0d 20 20 20 |   (if t|itle.   |
|00002d60| 20 20 20 20 20 20 20 20 | 20 74 69 74 6c 65 0d 20 |        | title. |
|00002d70| 20 20 20 20 20 20 20 20 | 20 20 20 22 20 22 29 29 |        |   " "))|
|00002d80| 29 0d 0d 28 64 65 66 75 | 6e 20 70 72 69 6e 74 2d |)..(defu|n print-|
|00002d90| 74 72 65 65 20 28 75 20 | 26 6b 65 79 20 74 69 74 |tree (u |&key tit|
|00002da0| 6c 65 29 0d 20 20 28 77 | 68 65 6e 20 74 69 74 6c |le).  (w|hen titl|
|00002db0| 65 0d 20 20 20 20 28 66 | 6f 72 6d 61 74 20 74 20 |e.    (f|ormat t |
|00002dc0| 22 7e 26 7e 61 7e 25 22 | 20 74 69 74 6c 65 29 29 |"~&~a~%"| title))|
|00002dd0| 0d 20 20 28 70 72 69 6e | 74 2d 74 72 65 65 31 20 |.  (prin|t-tree1 |
|00002de0| 75 20 31 20 2a 65 71 75 | 61 6c 2a 29 29 0d 0d 28 |u 1 *equ|al*))..(|
|00002df0| 64 65 66 75 6e 20 70 72 | 69 6e 74 2d 74 72 65 65 |defun pr|int-tree|
|00002e00| 31 20 28 75 20 6c 65 76 | 65 6c 20 64 69 72 29 0d |1 (u lev|el dir).|
|00002e10| 20 20 28 77 68 65 6e 20 | 75 0d 20 20 20 20 28 70 |  (when |u.    (p|
|00002e20| 72 69 6e 74 2d 6e 6f 64 | 65 20 75 20 6c 65 76 65 |rint-nod|e u leve|
|00002e30| 6c 20 64 69 72 29 0d 20 | 20 20 20 28 70 72 69 6e |l dir). |   (prin|
|00002e40| 74 2d 74 72 65 65 31 20 | 28 62 74 72 65 65 2d 6c |t-tree1 |(btree-l|
|00002e50| 65 66 74 20 75 29 20 28 | 31 2b 20 6c 65 76 65 6c |eft u) (|1+ level|
|00002e60| 29 20 2a 6c 65 66 74 2a | 29 0d 20 20 20 20 28 70 |) *left*|).    (p|
|00002e70| 72 69 6e 74 2d 74 72 65 | 65 31 20 28 62 74 72 65 |rint-tre|e1 (btre|
|00002e80| 65 2d 72 69 67 68 74 20 | 75 29 20 28 31 2b 20 6c |e-right |u) (1+ l|
|00002e90| 65 76 65 6c 29 20 2a 72 | 69 67 68 74 2a 29 29 29 |evel) *r|ight*)))|
|00002ea0| 0d 0d 28 64 65 66 75 6e | 20 70 72 69 6e 74 2d 72 |..(defun| print-r|
|00002eb0| 6f 6f 74 20 28 70 61 74 | 68 29 0d 20 20 28 70 72 |oot (pat|h).  (pr|
|00002ec0| 69 6e 74 2d 74 72 65 65 | 20 28 66 69 6e 64 2d 72 |int-tree| (find-r|
|00002ed0| 6f 6f 74 20 70 61 74 68 | 29 29 29 0d 0d 3b 3b 20 |oot path|)))..;; |
|00002ee0| 20 20 20 20 20 50 61 74 | 68 73 0d 28 64 65 66 75 |     Pat|hs.(defu|
|00002ef0| 6e 20 70 72 69 6e 74 2d | 70 61 74 68 20 28 70 61 |n print-|path (pa|
|00002f00| 74 68 20 26 6b 65 79 20 | 74 69 74 6c 65 29 0d 20 |th &key |title). |
|00002f10| 20 28 6c 65 74 20 28 6b | 65 79 20 64 69 72 65 63 | (let (k|ey direc|
|00002f20| 74 69 6f 6e 29 0d 20 20 | 20 20 28 66 6f 72 6d 61 |tion).  |  (forma|
|00002f30| 74 20 74 20 22 7e 26 7e | 61 20 50 61 74 68 20 6c |t t "~&~|a Path l|
|00002f40| 65 6e 67 74 68 20 7e 64 | 20 7e 25 22 0d 20 20 20 |ength ~d| ~%".   |
|00002f50| 20 20 20 20 20 20 20 20 | 20 28 69 66 20 74 69 74 |        | (if tit|
|00002f60| 6c 65 20 74 69 74 6c 65 | 20 22 20 22 29 0d 20 20 |le title| " ").  |
|00002f70| 20 20 20 20 20 20 20 20 | 20 20 28 6c 65 6e 67 74 |        |  (lengt|
|00002f80| 68 20 70 61 74 68 29 29 | 0d 20 20 20 20 28 64 6f |h path))|.    (do|
|00002f90| 6c 69 73 74 20 28 75 20 | 70 61 74 68 29 0d 20 20 |list (u |path).  |
|00002fa0| 20 20 20 20 28 73 65 74 | 66 20 64 69 72 65 63 74 |    (set|f direct|
|00002fb0| 69 6f 6e 20 28 62 74 72 | 61 69 6c 2d 64 69 72 20 |ion (btr|ail-dir |
|00002fc0| 75 29 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 6b |u).     |       k|
|00002fd0| 65 79 20 28 62 74 72 61 | 69 6c 2d 6e 6f 64 65 20 |ey (btra|il-node |
|00002fe0| 75 29 29 0d 20 20 20 20 | 20 20 28 69 66 20 64 69 |u)).    |  (if di|
|00002ff0| 72 65 63 74 69 6f 6e 0d | 20 20 20 20 20 20 20 20 |rection.|        |
|00003000| 28 66 6f 72 6d 61 74 20 | 74 20 22 7e 26 7e 73 20 |(format |t "~&~s |
|00003010| 7e 61 20 5b 7e 73 20 7e | 73 5d 20 7e 64 7e 25 22 |~a [~s ~|s] ~d~%"|
|00003020| 0d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.       |        |
|00003030| 20 28 62 74 72 65 65 2d | 6b 65 79 20 6b 65 79 29 | (btree-|key key)|
|00003040| 0d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |.       |        |
|00003050| 20 28 64 69 72 65 63 74 | 69 6f 6e 2d 73 74 72 69 | (direct|ion-stri|
|00003060| 6e 67 20 64 69 72 65 63 | 74 69 6f 6e 29 0d 20 20 |ng direc|tion).  |
|00003070| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 28 62 |        |      (b|
|00003080| 74 72 65 65 2d 6b 65 79 | 20 28 62 74 72 65 65 2d |tree-key| (btree-|
|00003090| 6d 69 6e 20 6b 65 79 29 | 29 0d 20 20 20 20 20 20 |min key)|).      |
|000030a0| 20 20 20 20 20 20 20 20 | 20 20 28 62 74 72 65 65 |        |  (btree|
|000030b0| 2d 6b 65 79 20 28 62 74 | 72 65 65 2d 6d 61 78 20 |-key (bt|ree-max |
|000030c0| 6b 65 79 29 29 0d 20 20 | 20 20 20 20 20 20 20 20 |key)).  |        |
|000030d0| 20 20 20 20 20 20 28 62 | 61 6c 61 6e 63 65 2d 73 |      (b|alance-s|
|000030e0| 74 72 69 6e 67 20 6b 65 | 79 29 29 0d 20 20 20 20 |tring ke|y)).    |
|000030f0| 20 20 20 20 28 66 6f 72 | 6d 61 74 20 74 20 22 7e |    (for|mat t "~|
|00003100| 26 7e 73 7e 25 22 20 6b | 65 79 29 29 29 29 29 0d |&~s~%" k|ey))))).|
|00003110| 0d 3b 3b 20 62 61 73 69 | 63 20 70 61 74 68 20 72 |.;; basi|c path r|
|00003120| 6f 75 74 69 6e 65 73 0d | 28 64 65 66 75 6e 20 69 |outines.|(defun i|
|00003130| 73 2d 72 6f 6f 74 20 28 | 70 61 74 68 29 0d 20 20 |s-root (|path).  |
|00003140| 28 6f 72 20 28 6e 75 6c | 6c 20 70 61 74 68 29 20 |(or (nul|l path) |
|00003150| 28 6e 75 6c 6c 20 28 72 | 65 73 74 20 70 61 74 68 |(null (r|est path|
|00003160| 29 29 29 29 0d 0d 3b 3b | 20 63 6f 6e 76 65 72 74 |))))..;;| convert|
|00003170| 69 6e 67 20 74 6f 2f 66 | 72 6f 6d 20 74 72 65 65 |ing to/f|rom tree|
|00003180| 73 20 61 6e 64 20 6c 69 | 73 74 73 0d 3b 3b 20 20 |s and li|sts.;;  |
|00003190| 28 74 6f 2d 62 74 72 65 | 65 20 28 66 72 6f 6d 2d |(to-btre|e (from-|
|000031a0| 62 74 72 65 65 20 74 72 | 65 65 29 20 6f 72 64 65 |btree tr|ee) orde|
|000031b0| 72 2d 66 75 6e 63 74 69 | 6f 6e 29 20 3d 20 74 72 |r-functi|on) = tr|
|000031c0| 65 65 0d 3b 3b 20 20 28 | 66 72 6f 6d 2d 62 74 72 |ee.;;  (|from-btr|
|000031d0| 65 65 20 28 74 6f 2d 62 | 74 72 65 65 20 6c 69 73 |ee (to-b|tree lis|
|000031e0| 74 20 6f 72 64 65 72 2d | 66 75 6e 63 74 69 6f 6e |t order-|function|
|000031f0| 29 29 20 3d 20 6c 69 73 | 74 20 0d 0d 28 64 65 66 |)) = lis|t ..(def|
|00003200| 75 6e 20 74 6f 2d 62 74 | 72 65 65 6b 20 28 6b 65 |un to-bt|reek (ke|
|00003210| 79 2d 6c 69 73 74 20 6f | 72 64 65 72 2d 66 75 6e |y-list o|rder-fun|
|00003220| 63 74 69 6f 6e 20 26 6b | 65 79 20 64 65 62 75 67 |ction &k|ey debug|
|00003230| 29 0d 20 20 22 43 6f 6e | 76 65 72 74 73 20 74 68 |).  "Con|verts th|
|00003240| 65 20 6c 69 73 74 20 6f | 66 20 6b 65 79 73 20 69 |e list o|f keys i|
|00003250| 6e 20 6b 65 79 2d 6c 69 | 73 74 20 74 6f 20 61 20 |n key-li|st to a |
|00003260| 62 74 72 65 65 20 77 69 | 74 68 20 0d 6b 65 79 20 |btree wi|th .key |
|00003270| 3d 20 20 76 61 6c 75 65 | 2e 20 20 55 73 65 73 20 |=  value|.  Uses |
|00003280| 74 68 65 20 6f 72 64 65 | 72 2d 66 75 6e 63 74 69 |the orde|r-functi|
|00003290| 6f 6e 0d 74 68 61 74 20 | 72 65 74 75 72 6e 73 20 |on.that |returns |
|000032a0| 2a 62 65 66 6f 72 65 2a | 20 2a 65 71 75 61 6c 2a |*before*| *equal*|
|000032b0| 20 2a 61 66 74 65 72 2a | 20 61 6e 64 20 6f 70 74 | *after*| and opt|
|000032c0| 69 6f 6e 61 6c 6c 79 20 | 70 72 69 6e 74 73 20 74 |ionally |prints t|
|000032d0| 68 65 20 0d 74 72 65 65 | 20 61 73 20 69 74 20 69 |he .tree| as it i|
|000032e0| 73 20 62 65 69 6e 67 20 | 61 73 73 65 6d 62 6c 65 |s being |assemble|
|000032f0| 64 22 0d 20 20 28 6c 65 | 74 20 28 72 6f 6f 74 20 |d".  (le|t (root |
|00003300| 70 61 74 68 20 61 2d 6b | 65 79 20 74 69 74 6c 65 |path a-k|ey title|
|00003310| 29 0d 20 20 20 20 28 77 | 68 65 6e 20 6b 65 79 2d |).    (w|hen key-|
|00003320| 6c 69 73 74 0d 20 20 20 | 20 20 20 28 73 65 74 66 |list.   |   (setf|
|00003330| 20 72 6f 6f 74 20 28 6d | 61 6b 65 2d 62 74 72 65 | root (m|ake-btre|
|00003340| 65 20 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |e .     |        |
|00003350| 20 20 20 20 20 3a 6b 65 | 79 20 28 73 65 74 71 20 |     :ke|y (setq |
|00003360| 61 2d 6b 65 79 20 28 70 | 6f 70 20 6b 65 79 2d 6c |a-key (p|op key-l|
|00003370| 69 73 74 29 29 0d 20 20 | 20 20 20 20 20 20 20 20 |ist)).  |        |
|00003380| 20 20 20 20 20 20 20 20 | 3a 76 61 6c 20 61 2d 6b |        |:val a-k|
|00003390| 65 79 29 0d 20 20 20 20 | 20 20 20 20 20 20 20 20 |ey).    |        |
|000033a0| 70 61 74 68 20 28 72 6f | 6f 74 2d 70 61 74 68 20 |path (ro|ot-path |
|000033b0| 72 6f 6f 74 29 29 0d 20 | 20 20 20 20 20 28 6c 6f |root)). |     (lo|
|000033c0| 6f 70 20 66 6f 72 20 61 | 2d 6b 65 79 20 69 6e 20 |op for a|-key in |
|000033d0| 6b 65 79 2d 6c 69 73 74 | 0d 20 20 20 20 20 20 20 |key-list|.       |
|000033e0| 20 20 20 20 20 64 6f 20 | 28 73 65 74 66 20 70 61 |     do |(setf pa|
|000033f0| 74 68 20 28 61 64 64 2d | 6e 6f 64 65 20 61 2d 6b |th (add-|node a-k|
|00003400| 65 79 20 61 2d 6b 65 79 | 20 28 72 6f 6f 74 2d 70 |ey a-key| (root-p|
|00003410| 61 74 68 20 72 6f 6f 74 | 29 20 6f 72 64 65 72 2d |ath root|) order-|
|00003420| 66 75 6e 63 74 69 6f 6e | 29 29 0d 20 20 20 20 20 |function|)).     |
|00003430| 20 20 20 20 20 20 20 28 | 73 65 74 71 20 72 6f 6f |       (|setq roo|
|00003440| 74 20 28 66 69 6e 64 2d | 72 6f 6f 74 20 70 61 74 |t (find-|root pat|
|00003450| 68 29 29 0d 20 20 20 20 | 20 20 20 20 20 20 20 20 |h)).    |        |
|00003460| 28 77 68 65 6e 20 64 65 | 62 75 67 0d 20 20 20 20 |(when de|bug.    |
|00003470| 20 20 20 20 20 20 20 20 | 20 20 28 73 65 74 66 20 |        |  (setf |
|00003480| 74 69 74 6c 65 20 28 66 | 6f 72 6d 61 74 20 6e 69 |title (f|ormat ni|
|00003490| 6c 20 22 2a 2a 61 64 64 | 20 7e 73 22 20 61 2d 6b |l "**add| ~s" a-k|
|000034a0| 65 79 29 29 20 0d 20 20 | 20 20 20 20 20 20 20 20 |ey)) .  |        |
|000034b0| 20 20 20 20 28 70 72 69 | 6e 74 2d 70 61 74 68 20 |    (pri|nt-path |
|000034c0| 70 61 74 68 20 3a 74 69 | 74 6c 65 20 74 69 74 6c |path :ti|tle titl|
|000034d0| 65 29 20 0d 20 20 20 20 | 20 20 20 20 20 20 20 20 |e) .    |        |
|000034e0| 20 20 28 70 72 69 6e 74 | 2d 74 72 65 65 20 72 6f |  (print|-tree ro|
|000034f0| 6f 74 20 3a 74 69 74 6c | 65 20 74 69 74 6c 65 29 |ot :titl|e title)|
|00003500| 29 29 0d 20 20 20 20 20 | 20 72 6f 6f 74 29 29 29 |)).     | root)))|
|00003510| 0d 0d 28 64 65 66 75 6e | 20 74 6f 2d 62 74 72 65 |..(defun| to-btre|
|00003520| 65 20 28 6b 65 79 2d 6c | 69 73 74 20 6f 72 64 65 |e (key-l|ist orde|
|00003530| 72 2d 66 75 6e 63 74 69 | 6f 6e 20 26 6b 65 79 20 |r-functi|on &key |
|00003540| 64 65 62 75 67 29 0d 20 | 20 22 43 6f 6e 76 65 72 |debug). | "Conver|
|00003550| 74 73 20 74 68 65 20 6c | 69 73 74 20 6f 66 20 28 |ts the l|ist of (|
|00003560| 6b 65 79 20 76 61 6c 75 | 65 29 20 69 6e 20 6b 65 |key valu|e) in ke|
|00003570| 79 2d 6c 69 73 74 20 74 | 6f 20 61 20 62 74 72 65 |y-list t|o a btre|
|00003580| 65 2e 0d 55 73 65 73 20 | 74 68 65 20 6f 72 64 65 |e..Uses |the orde|
|00003590| 72 2d 66 75 6e 63 74 69 | 6f 6e 20 74 68 61 74 20 |r-functi|on that |
|000035a0| 72 65 74 75 72 6e 73 20 | 2a 62 65 66 6f 72 65 2a |returns |*before*|
|000035b0| 20 2a 65 71 75 61 6c 2a | 20 2a 61 66 74 65 72 2a | *equal*| *after*|
|000035c0| 20 0d 61 6e 64 20 6f 70 | 74 69 6f 6e 61 6c 6c 79 | .and op|tionally|
|000035d0| 20 70 72 69 6e 74 73 20 | 74 68 65 20 0d 74 72 65 | prints |the .tre|
|000035e0| 65 20 61 73 20 69 74 20 | 69 73 20 62 65 69 6e 67 |e as it |is being|
|000035f0| 20 61 73 73 65 6d 62 6c | 65 64 22 0d 20 20 28 6c | assembl|ed".  (l|
|00003600| 65 74 20 28 72 6f 6f 74 | 20 70 61 74 68 20 6b 65 |et (root| path ke|
|00003610| 79 2d 70 61 72 74 20 74 | 69 74 6c 65 29 0d 20 20 |y-part t|itle).  |
|00003620| 20 20 28 77 68 65 6e 20 | 6b 65 79 2d 6c 69 73 74 |  (when |key-list|
|00003630| 0d 20 20 20 20 20 20 28 | 73 65 74 66 20 6b 65 79 |.      (|setf key|
|00003640| 2d 70 61 72 74 20 28 70 | 6f 70 20 6b 65 79 2d 6c |-part (p|op key-l|
|00003650| 69 73 74 29 0d 20 20 20 | 20 20 20 20 20 20 20 20 |ist).   |        |
|00003660| 20 72 6f 6f 74 20 28 6d | 61 6b 65 2d 62 74 72 65 | root (m|ake-btre|
|00003670| 65 20 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |e .     |        |
|00003680| 20 20 20 20 20 3a 6b 65 | 79 20 28 66 69 72 73 74 |     :ke|y (first|
|00003690| 20 6b 65 79 2d 70 61 72 | 74 29 0d 20 20 20 20 20 | key-par|t).     |
|000036a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 3a 76 61 |        |     :va|
|000036b0| 6c 20 28 73 65 63 6f 6e | 64 20 6b 65 79 2d 70 61 |l (secon|d key-pa|
|000036c0| 72 74 29 0d 20 20 20 20 | 20 20 20 20 20 20 20 20 |rt).    |        |
|000036d0| 20 20 20 20 20 20 3a 62 | 61 6c 61 6e 63 65 20 2a |      :b|alance *|
|000036e0| 62 61 6c 61 6e 63 65 64 | 2a 29 0d 20 20 20 20 20 |balanced|*).     |
|000036f0| 20 20 20 20 20 20 20 70 | 61 74 68 20 28 72 6f 6f |       p|ath (roo|
|00003700| 74 2d 70 61 74 68 20 72 | 6f 6f 74 29 29 0d 20 20 |t-path r|oot)).  |
|00003710| 20 20 20 20 28 64 6f 6c | 69 73 74 20 28 6b 65 79 |    (dol|ist (key|
|00003720| 2d 70 61 72 74 20 6b 65 | 79 2d 6c 69 73 74 29 0d |-part ke|y-list).|
|00003730| 20 20 20 20 20 20 20 20 | 28 73 65 74 71 20 70 61 |        |(setq pa|
|00003740| 74 68 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |th.     |        |
|00003750| 20 28 61 64 64 2d 6e 6f | 64 65 20 28 66 69 72 73 | (add-no|de (firs|
|00003760| 74 20 6b 65 79 2d 70 61 | 72 74 29 0d 20 20 20 20 |t key-pa|rt).    |
|00003770| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003780| 20 20 20 20 28 73 65 63 | 6f 6e 64 20 6b 65 79 2d |    (sec|ond key-|
|00003790| 70 61 72 74 29 0d 20 20 | 20 20 20 20 20 20 20 20 |part).  |        |
|000037a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 70 61 |        |      pa|
|000037b0| 74 68 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |th.     |        |
|000037c0| 20 20 20 20 20 20 20 20 | 20 20 20 6f 72 64 65 72 |        |   order|
|000037d0| 2d 66 75 6e 63 74 69 6f | 6e 29 29 0d 20 20 20 20 |-functio|n)).    |
|000037e0| 20 20 20 20 28 77 68 65 | 6e 20 64 65 62 75 67 0d |    (whe|n debug.|
|000037f0| 20 20 20 20 20 20 20 20 | 20 20 28 73 65 74 66 20 |        |  (setf |
|00003800| 74 69 74 6c 65 20 28 66 | 6f 72 6d 61 74 20 6e 69 |title (f|ormat ni|
|00003810| 6c 20 22 2a 2a 61 64 64 | 20 7e 73 22 20 28 66 69 |l "**add| ~s" (fi|
|00003820| 72 73 74 20 6b 65 79 2d | 70 61 72 74 29 29 29 20 |rst key-|part))) |
|00003830| 0d 20 20 20 20 20 20 20 | 20 20 20 28 70 72 69 6e |.       |   (prin|
|00003840| 74 2d 70 61 74 68 20 70 | 61 74 68 20 3a 74 69 74 |t-path p|ath :tit|
|00003850| 6c 65 20 74 69 74 6c 65 | 29 20 0d 20 20 20 20 20 |le title|) .     |
|00003860| 20 20 20 20 20 28 70 72 | 69 6e 74 2d 74 72 65 65 |     (pr|int-tree|
|00003870| 20 72 6f 6f 74 20 3a 74 | 69 74 6c 65 20 74 69 74 | root :t|itle tit|
|00003880| 6c 65 29 29 29 0d 20 20 | 20 20 20 20 72 6f 6f 74 |le))).  |    root|
|00003890| 29 29 29 0d 0d 28 64 65 | 66 75 6e 20 66 72 6f 6d |)))..(de|fun from|
|000038a0| 2d 62 74 72 65 65 20 28 | 74 72 65 65 29 0d 20 20 |-btree (|tree).  |
|000038b0| 22 43 6f 6e 76 65 72 74 | 20 61 20 62 74 72 65 65 |"Convert| a btree|
|000038c0| 20 74 6f 20 61 20 6c 69 | 73 74 20 6f 66 20 74 68 | to a li|st of th|
|000038d0| 65 20 66 6f 72 6d 20 28 | 28 6b 65 79 20 76 61 6c |e form (|(key val|
|000038e0| 29 20 2e 2e 2e 20 28 6b | 65 79 6e 20 76 61 6c 6e |) ... (k|eyn valn|
|000038f0| 29 29 20 73 6f 72 74 65 | 64 20 62 79 20 6b 65 79 |)) sorte|d by key|
|00003900| 22 0d 20 20 28 6e 72 65 | 76 65 72 73 65 20 28 66 |".  (nre|verse (f|
|00003910| 72 6f 6d 2d 62 74 72 65 | 65 31 20 74 72 65 65 20 |rom-btre|e1 tree |
|00003920| 6e 69 6c 29 29 29 0d 0d | 28 64 65 66 75 6e 20 66 |nil)))..|(defun f|
|00003930| 72 6f 6d 2d 62 74 72 65 | 65 31 20 28 74 72 65 65 |rom-btre|e1 (tree|
|00003940| 20 6e 6f 64 65 73 29 0d | 20 20 3b 3b 20 63 6f 76 | nodes).|  ;; cov|
|00003950| 65 72 74 20 74 6f 20 61 | 20 6c 69 73 74 20 73 6f |ert to a| list so|
|00003960| 72 74 65 64 20 62 79 20 | 6b 65 79 20 69 6e 20 64 |rted by |key in d|
|00003970| 65 73 63 65 6e 64 69 6e | 67 20 6f 72 64 65 72 0d |escendin|g order.|
|00003980| 20 20 28 6c 65 74 20 28 | 70 72 69 6e 74 2d 6e 6f |  (let (|print-no|
|00003990| 64 65 29 0d 20 20 20 20 | 28 6f 70 65 72 61 74 65 |de).    |(operate|
|000039a0| 2d 6f 6e 2d 74 72 65 65 | 20 28 6e 6f 64 65 20 74 |-on-tree| (node t|
|000039b0| 72 65 65 20 6c 65 66 74 | 20 72 69 67 68 74 29 0d |ree left| right).|
|000039c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000039d0| 20 20 20 20 20 3a 6e 6f | 64 65 2d 61 63 74 69 6f |     :no|de-actio|
|000039e0| 6e 20 28 73 65 74 71 20 | 70 72 69 6e 74 2d 6e 6f |n (setq |print-no|
|000039f0| 64 65 20 74 29 0d 20 20 | 20 20 20 20 20 20 20 20 |de t).  |        |
|00003a00| 20 20 20 20 20 20 20 20 | 20 20 20 3a 62 72 61 6e |        |   :bran|
|00003a10| 63 68 2d 61 63 74 69 6f | 6e 20 28 69 66 20 28 65 |ch-actio|n (if (e|
|00003a20| 71 20 6e 6f 64 65 20 6c | 65 66 74 29 0d 20 20 20 |q node l|eft).   |
|00003a30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003a40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003a50| 20 20 20 28 73 65 74 71 | 20 6e 6f 64 65 73 20 28 |   (setq| nodes (|
|00003a60| 66 72 6f 6d 2d 62 74 72 | 65 65 31 20 6e 6f 64 65 |from-btr|ee1 node|
|00003a70| 20 6e 6f 64 65 73 29 29 | 0d 20 20 20 20 20 20 20 | nodes))|.       |
|00003a80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003a90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 28 |        |       (|
|00003aa0| 70 72 6f 67 6e 0d 20 20 | 20 20 20 20 20 20 20 20 |progn.  |        |
|00003ab0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003ac0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 28 70 |        |      (p|
|00003ad0| 75 73 68 20 20 28 6c 69 | 73 74 20 28 62 74 72 65 |ush  (li|st (btre|
|00003ae0| 65 2d 6b 65 79 20 74 72 | 65 65 29 0d 20 20 20 20 |e-key tr|ee).    |
|00003af0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003b00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003b10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003b20| 20 28 62 74 72 65 65 2d | 76 61 6c 20 74 72 65 65 | (btree-|val tree|
|00003b30| 29 29 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |)).     |        |
|00003b40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003b50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003b60| 20 20 6e 6f 64 65 73 29 | 0d 20 20 20 20 20 20 20 |  nodes)|.       |
|00003b70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003b80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003b90| 20 28 73 65 74 71 20 70 | 72 69 6e 74 2d 6e 6f 64 | (setq p|rint-nod|
|00003ba0| 65 20 6e 69 6c 29 0d 20 | 20 20 20 20 20 20 20 20 |e nil). |        |
|00003bb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003bc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 28 |        |       (|
|00003bd0| 73 65 74 71 20 6e 6f 64 | 65 73 20 28 66 72 6f 6d |setq nod|es (from|
|00003be0| 2d 62 74 72 65 65 31 20 | 6e 6f 64 65 20 6e 6f 64 |-btree1 |node nod|
|00003bf0| 65 73 29 29 29 29 0d 20 | 20 20 20 20 20 20 20 20 |es)))). |        |
|00003c00| 20 20 20 20 20 20 20 20 | 20 20 20 20 3a 72 65 74 |        |    :ret|
|00003c10| 75 72 6e 20 28 70 72 6f | 67 6e 20 0d 20 20 20 20 |urn (pro|gn .    |
|00003c20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003c30| 20 20 20 20 20 20 20 20 | 20 20 20 28 77 68 65 6e |        |   (when|
|00003c40| 20 70 72 69 6e 74 2d 6e | 6f 64 65 0d 20 20 20 20 | print-n|ode.    |
|00003c50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003c60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 28 70 75 |        |     (pu|
|00003c70| 73 68 20 20 28 6c 69 73 | 74 20 28 62 74 72 65 65 |sh  (lis|t (btree|
|00003c80| 2d 6b 65 79 20 74 72 65 | 65 29 0d 20 20 20 20 20 |-key tre|e).     |
|00003c90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003ca0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003cb0| 20 20 20 20 20 20 20 20 | 20 28 62 74 72 65 65 2d |        | (btree-|
|00003cc0| 76 61 6c 20 74 72 65 65 | 29 29 0d 20 20 20 20 20 |val tree|)).     |
|00003cd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003ce0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003cf0| 20 20 20 6e 6f 64 65 73 | 29 29 0d 20 20 20 20 20 |   nodes|)).     |
|00003d00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00003d10| 20 20 20 20 20 20 20 20 | 20 20 6e 6f 64 65 73 29 |        |  nodes)|
|00003d20| 29 29 29 0d 0d 3b 3b 20 | 2d 2d 3e 20 62 61 73 69 |)))..;; |--> basi|
|00003d30| 63 20 6e 6f 64 65 20 72 | 6f 75 74 69 6e 65 73 0d |c node r|outines.|
|00003d40| 28 64 65 66 75 6e 20 63 | 68 65 63 6b 2d 6c 65 61 |(defun c|heck-lea|
|00003d50| 66 20 28 6e 6f 64 65 29 | 0d 20 20 22 46 6f 72 20 |f (node)|.  "For |
|00003d60| 61 20 6c 65 61 66 20 6e | 6f 64 65 2c 20 66 69 6c |a leaf n|ode, fil|
|00003d70| 6c 73 20 69 6e 20 74 68 | 65 20 6d 69 6e 20 61 6e |ls in th|e min an|
|00003d80| 64 20 6d 61 78 20 61 6e | 64 20 62 61 6c 61 6e 63 |d max an|d balanc|
|00003d90| 65 20 66 69 65 6c 64 73 | 2e 22 0d 20 20 28 77 68 |e fields|.".  (wh|
|00003da0| 65 6e 20 28 61 6e 64 20 | 6e 6f 64 65 20 28 69 73 |en (and |node (is|
|00003db0| 2d 6c 65 61 66 20 6e 6f | 64 65 29 29 0d 20 20 20 |-leaf no|de)).   |
|00003dc0| 20 28 73 65 74 66 20 28 | 62 74 72 65 65 2d 62 61 | (setf (|btree-ba|
|00003dd0| 6c 61 6e 63 65 20 6e 6f | 64 65 29 20 2a 62 61 6c |lance no|de) *bal|
|00003de0| 61 6e 63 65 64 2a 0d 20 | 20 20 20 20 20 20 20 20 |anced*. |        |
|00003df0| 20 28 62 74 72 65 65 2d | 6d 61 78 20 6e 6f 64 65 | (btree-|max node|
|00003e00| 29 20 6e 69 6c 0d 20 20 | 20 20 20 20 20 20 20 20 |) nil.  |        |
|00003e10| 28 62 74 72 65 65 2d 6d | 69 6e 20 6e 6f 64 65 29 |(btree-m|in node)|
|00003e20| 20 6e 69 6c 29 29 29 0d | 0d 28 64 65 66 75 6e 20 | nil))).|.(defun |
|00003e30| 69 73 2d 6c 65 61 66 20 | 28 6e 6f 64 65 29 0d 20 |is-leaf |(node). |
|00003e40| 20 22 52 65 74 75 72 6e | 73 20 74 20 69 66 66 20 | "Return|s t iff |
|00003e50| 74 68 65 20 6e 6f 64 65 | 20 69 73 20 61 20 6c 65 |the node| is a le|
|00003e60| 61 66 20 6e 6f 64 65 22 | 0d 20 20 28 6f 72 20 28 |af node"|.  (or (|
|00003e70| 6e 75 6c 6c 20 6e 6f 64 | 65 29 0d 20 20 20 20 20 |null nod|e).     |
|00003e80| 20 28 61 6e 64 20 28 6e | 75 6c 6c 20 28 62 74 72 | (and (n|ull (btr|
|00003e90| 65 65 2d 6c 65 66 74 20 | 6e 6f 64 65 29 29 0d 20 |ee-left |node)). |
|00003ea0| 20 20 20 20 20 20 20 20 | 20 20 28 6e 75 6c 6c 20 |        |  (null |
|00003eb0| 28 62 74 72 65 65 2d 72 | 69 67 68 74 20 6e 6f 64 |(btree-r|ight nod|
|00003ec0| 65 29 29 29 29 29 0d 0d | 28 64 65 66 75 6e 20 72 |e)))))..|(defun r|
|00003ed0| 65 70 6c 61 63 65 2d 6e | 6f 64 65 20 28 73 6f 75 |eplace-n|ode (sou|
|00003ee0| 72 63 65 20 72 65 70 6c | 61 63 65 6d 65 6e 74 29 |rce repl|acement)|
|00003ef0| 0d 20 20 22 57 68 65 6e | 20 73 6f 75 72 63 65 20 |.  "When| source |
|00003f00| 61 6e 64 20 72 65 70 6c | 61 63 65 6d 65 6e 74 20 |and repl|acement |
|00003f10| 61 72 65 20 6c 69 73 74 | 73 2c 20 69 6e 74 65 72 |are list|s, inter|
|00003f20| 63 68 61 6e 67 65 73 20 | 74 68 65 20 74 77 6f 20 |changes |the two |
|00003f30| 6c 69 73 74 73 22 0d 20 | 20 28 77 68 65 6e 20 28 |lists". | (when (|
|00003f40| 61 6e 64 20 73 6f 75 72 | 63 65 20 28 6c 69 73 74 |and sour|ce (list|
|00003f50| 70 20 73 6f 75 72 63 65 | 29 20 28 6c 69 73 74 70 |p source|) (listp|
|00003f60| 20 72 65 70 6c 61 63 65 | 6d 65 6e 74 29 29 0d 20 | replace|ment)). |
|00003f70| 20 20 20 28 73 65 74 66 | 20 28 66 69 72 73 74 20 |   (setf| (first |
|00003f80| 73 6f 75 72 63 65 29 20 | 28 66 69 72 73 74 20 72 |source) |(first r|
|00003f90| 65 70 6c 61 63 65 6d 65 | 6e 74 29 0d 20 20 20 20 |eplaceme|nt).    |
|00003fa0| 20 20 20 20 20 20 28 72 | 65 73 74 20 73 6f 75 72 |      (r|est sour|
|00003fb0| 63 65 29 20 28 72 65 73 | 74 20 72 65 70 6c 61 63 |ce) (res|t replac|
|00003fc0| 65 6d 65 6e 74 29 29 29 | 29 0d 0d 28 64 65 66 75 |ement)))|)..(defu|
|00003fd0| 6e 20 69 6e 74 65 72 63 | 68 61 6e 67 65 2d 6e 6f |n interc|hange-no|
|00003fe0| 64 65 73 20 28 6e 6f 64 | 65 31 20 6e 6f 64 65 32 |des (nod|e1 node2|
|00003ff0| 29 0d 20 20 22 49 6e 74 | 65 72 63 68 61 6e 67 65 |).  "Int|erchange|
|00004000| 73 20 6e 6f 64 65 31 20 | 61 6e 64 20 6e 6f 64 65 |s node1 |and node|
|00004010| 32 22 0d 20 20 28 6c 65 | 74 20 28 28 74 65 6d 70 |2".  (le|t ((temp|
|00004020| 2d 6e 6f 64 65 20 28 63 | 6f 70 79 2d 6c 69 73 74 |-node (c|opy-list|
|00004030| 20 6e 6f 64 65 31 29 29 | 29 0d 20 20 20 20 28 72 | node1))|).    (r|
|00004040| 65 70 6c 61 63 65 2d 6e | 6f 64 65 20 6e 6f 64 65 |eplace-n|ode node|
|00004050| 31 20 6e 6f 64 65 32 29 | 0d 20 20 20 20 28 72 65 |1 node2)|.    (re|
|00004060| 70 6c 61 63 65 2d 6e 6f | 64 65 20 6e 6f 64 65 31 |place-no|de node1|
|00004070| 20 74 65 6d 70 2d 6e 6f | 64 65 29 29 29 0d 0d 28 | temp-no|de)))..(|
|00004080| 64 65 66 75 6e 20 73 77 | 61 70 2d 6b 65 79 20 28 |defun sw|ap-key (|
|00004090| 6e 6f 64 65 31 20 6e 6f | 64 65 32 20 26 6b 65 79 |node1 no|de2 &key|
|000040a0| 20 62 61 6c 61 6e 63 65 | 29 0d 20 20 22 53 77 61 | balance|).  "Swa|
|000040b0| 70 73 20 74 68 65 20 6b | 65 79 73 20 61 73 73 6f |ps the k|eys asso|
|000040c0| 63 69 61 74 65 64 20 77 | 69 74 68 20 62 74 72 65 |ciated w|ith btre|
|000040d0| 64 65 20 6e 6f 64 65 73 | 20 6e 6f 64 65 31 20 61 |de nodes| node1 a|
|000040e0| 6e 64 20 6e 6f 64 65 32 | 20 61 6e 64 20 6f 70 74 |nd node2| and opt|
|000040f0| 69 6f 6e 61 6c 6c 79 20 | 73 77 61 70 73 20 74 68 |ionally |swaps th|
|00004100| 65 20 62 61 6c 61 6e 63 | 65 22 0d 20 20 28 75 6e |e balanc|e".  (un|
|00004110| 6c 65 73 73 20 28 61 6e | 64 20 6e 6f 64 65 31 20 |less (an|d node1 |
|00004120| 6e 6f 64 65 32 29 0d 20 | 20 20 20 28 62 72 65 61 |node2). |   (brea|
|00004130| 6b 20 22 62 61 64 2d 73 | 77 61 70 2d 6e 6f 64 65 |k "bad-s|wap-node|
|00004140| 73 22 29 29 0d 20 20 28 | 72 6f 74 61 74 65 66 20 |s")).  (|rotatef |
|00004150| 28 62 74 72 65 65 2d 6b | 65 79 20 6e 6f 64 65 31 |(btree-k|ey node1|
|00004160| 29 20 28 62 74 72 65 65 | 2d 6b 65 79 20 6e 6f 64 |) (btree|-key nod|
|00004170| 65 32 29 29 0d 20 20 28 | 72 6f 74 61 74 65 66 20 |e2)).  (|rotatef |
|00004180| 28 62 74 72 65 65 2d 76 | 61 6c 20 6e 6f 64 65 31 |(btree-v|al node1|
|00004190| 29 20 28 62 74 72 65 65 | 2d 76 61 6c 20 6e 6f 64 |) (btree|-val nod|
|000041a0| 65 32 29 29 0d 20 20 28 | 77 68 65 6e 20 62 61 6c |e2)).  (|when bal|
|000041b0| 61 6e 63 65 0d 20 20 20 | 20 28 72 6f 74 61 74 65 |ance.   | (rotate|
|000041c0| 66 20 28 62 74 72 65 65 | 2d 62 61 6c 61 6e 63 65 |f (btree|-balance|
|000041d0| 20 6e 6f 64 65 31 29 20 | 28 62 74 72 65 65 2d 62 | node1) |(btree-b|
|000041e0| 61 6c 61 6e 63 65 20 6e | 6f 64 65 32 29 29 29 29 |alance n|ode2))))|
|000041f0| 0d 0d 28 64 65 66 75 6e | 20 63 6f 70 79 2d 69 6e |..(defun| copy-in|
|00004200| 66 6f 20 28 73 6f 75 72 | 63 65 20 64 65 73 74 69 |fo (sour|ce desti|
|00004210| 6e 61 74 69 6f 6e 20 26 | 6b 65 79 20 6c 65 66 74 |nation &|key left|
|00004220| 20 72 69 67 68 74 20 6d | 61 78 20 6d 69 6e 20 62 | right m|ax min b|
|00004230| 61 6c 61 6e 63 65 29 0d | 20 20 22 43 6f 70 69 65 |alance).|  "Copie|
|00004240| 73 20 73 65 6c 65 63 74 | 65 64 20 66 69 65 6c 64 |s select|ed field|
|00004250| 73 20 66 72 6f 6d 20 74 | 68 65 20 73 6f 75 72 63 |s from t|he sourc|
|00004260| 65 20 74 6f 20 74 68 65 | 20 64 65 73 74 69 6e 61 |e to the| destina|
|00004270| 74 69 6f 6e 20 6e 6f 64 | 65 2e 0d 42 79 20 64 65 |tion nod|e..By de|
|00004280| 66 61 75 6c 74 20 72 65 | 70 6c 61 63 65 73 20 74 |fault re|places t|
|00004290| 68 65 20 6b 65 79 20 61 | 6e 64 20 76 61 6c 75 65 |he key a|nd value|
|000042a0| 73 20 66 69 65 6c 64 73 | 20 69 6e 20 74 68 65 20 |s fields| in the |
|000042b0| 64 65 73 74 69 6e 61 74 | 69 6f 6e 20 62 79 20 74 |destinat|ion by t|
|000042c0| 68 65 20 73 6f 75 72 63 | 65 2e 0d 57 68 65 6e 20 |he sourc|e..When |
|000042d0| 74 68 65 20 6b 65 79 77 | 6f 72 64 20 70 61 72 61 |the keyw|ord para|
|000042e0| 6d 65 74 65 72 20 76 61 | 6c 75 65 73 20 61 72 65 |meter va|lues are|
|000042f0| 20 6e 6f 6e 20 6e 69 6c | 2c 20 72 65 70 6c 61 63 | non nil|, replac|
|00004300| 65 73 20 74 68 65 73 65 | 20 66 69 65 6c 64 73 20 |es these| fields |
|00004310| 61 73 20 77 65 6c 6c 22 | 0d 20 20 28 75 6e 6c 65 |as well"|.  (unle|
|00004320| 73 73 20 28 61 6e 64 20 | 73 6f 75 72 63 65 20 64 |ss (and |source d|
|00004330| 65 73 74 69 6e 61 74 69 | 6f 6e 29 0d 20 20 20 20 |estinati|on).    |
|00004340| 28 62 72 65 61 6b 20 22 | 62 61 64 2d 63 6f 70 79 |(break "|bad-copy|
|00004350| 22 29 29 0d 20 20 28 73 | 65 74 66 20 28 62 74 72 |")).  (s|etf (btr|
|00004360| 65 65 2d 6b 65 79 20 64 | 65 73 74 69 6e 61 74 69 |ee-key d|estinati|
|00004370| 6f 6e 29 20 28 62 74 72 | 65 65 2d 6b 65 79 20 73 |on) (btr|ee-key s|
|00004380| 6f 75 72 63 65 29 0d 20 | 20 20 20 20 20 20 20 28 |ource). |       (|
|00004390| 62 74 72 65 65 2d 76 61 | 6c 20 64 65 73 74 69 6e |btree-va|l destin|
|000043a0| 61 74 69 6f 6e 29 20 28 | 62 74 72 65 65 2d 76 61 |ation) (|btree-va|
|000043b0| 6c 20 73 6f 75 72 63 65 | 29 29 0d 20 20 28 77 68 |l source|)).  (wh|
|000043c0| 65 6e 20 6c 65 66 74 0d | 20 20 20 20 28 73 65 74 |en left.|    (set|
|000043d0| 66 20 28 62 74 72 65 65 | 2d 6c 65 66 74 20 64 65 |f (btree|-left de|
|000043e0| 73 74 69 6e 61 74 69 6f | 6e 29 20 28 62 74 72 65 |stinatio|n) (btre|
|000043f0| 65 2d 6c 65 66 74 20 73 | 6f 75 72 63 65 29 29 29 |e-left s|ource)))|
|00004400| 0d 20 20 28 77 68 65 6e | 20 72 69 67 68 74 0d 20 |.  (when| right. |
|00004410| 20 20 20 28 73 65 74 66 | 20 28 62 74 72 65 65 2d |   (setf| (btree-|
|00004420| 72 69 67 68 74 20 64 65 | 73 74 69 6e 61 74 69 6f |right de|stinatio|
|00004430| 6e 29 20 28 62 74 72 65 | 65 2d 72 69 67 68 74 20 |n) (btre|e-right |
|00004440| 73 6f 75 72 63 65 29 29 | 29 0d 20 20 28 77 68 65 |source))|).  (whe|
|00004450| 6e 20 6d 61 78 0d 20 20 | 20 20 28 73 65 74 66 20 |n max.  |  (setf |
|00004460| 28 62 74 72 65 65 2d 6d | 61 78 20 64 65 73 74 69 |(btree-m|ax desti|
|00004470| 6e 61 74 69 6f 6e 29 20 | 28 62 74 72 65 65 2d 6d |nation) |(btree-m|
|00004480| 61 78 20 73 6f 75 72 63 | 65 29 29 29 0d 20 20 28 |ax sourc|e))).  (|
|00004490| 77 68 65 6e 20 6d 69 6e | 0d 20 20 20 20 28 73 65 |when min|.    (se|
|000044a0| 74 66 20 28 62 74 72 65 | 65 2d 6d 69 6e 20 64 65 |tf (btre|e-min de|
|000044b0| 73 74 69 6e 61 74 69 6f | 6e 29 20 28 62 74 72 65 |stinatio|n) (btre|
|000044c0| 65 2d 6d 69 6e 20 73 6f | 75 72 63 65 29 29 29 0d |e-min so|urce))).|
|000044d0| 20 20 28 77 68 65 6e 20 | 62 61 6c 61 6e 63 65 0d |  (when |balance.|
|000044e0| 20 20 20 20 28 73 65 74 | 66 20 28 62 74 72 65 65 |    (set|f (btree|
|000044f0| 2d 62 61 6c 61 6e 63 65 | 20 64 65 73 74 69 6e 61 |-balance| destina|
|00004500| 74 69 6f 6e 29 20 28 62 | 74 72 65 65 2d 62 61 6c |tion) (b|tree-bal|
|00004510| 61 6e 63 65 20 73 6f 75 | 72 63 65 29 29 29 0d 20 |ance sou|rce))). |
|00004520| 20 64 65 73 74 69 6e 61 | 74 69 6f 6e 29 0d 0d 3b | destina|tion)..;|
|00004530| 3b 20 2d 2d 3e 20 6d 69 | 6e 2f 6d 61 78 20 72 6f |; --> mi|n/max ro|
|00004540| 75 74 69 6e 65 73 0d 0d | 28 64 65 66 75 6e 20 67 |utines..|(defun g|
|00004550| 65 74 2d 6d 61 78 20 28 | 6e 6f 64 65 29 0d 20 20 |et-max (|node).  |
|00004560| 22 52 65 74 75 72 6e 20 | 74 68 65 20 72 69 67 68 |"Return |the righ|
|00004570| 74 6d 6f 73 74 20 6e 6f | 64 65 20 69 6e 20 74 68 |tmost no|de in th|
|00004580| 65 20 74 72 65 65 20 72 | 6f 6f 74 65 64 20 61 74 |e tree r|ooted at|
|00004590| 20 6e 6f 64 65 22 0d 20 | 20 28 6f 72 20 28 62 74 | node". | (or (bt|
|000045a0| 72 65 65 2d 6d 61 78 20 | 6e 6f 64 65 29 0d 20 20 |ree-max |node).  |
|000045b0| 20 20 20 20 6e 6f 64 65 | 29 29 0d 0d 28 64 65 66 |    node|))..(def|
|000045c0| 75 6e 20 67 65 74 2d 6d | 69 6e 20 28 6e 6f 64 65 |un get-m|in (node|
|000045d0| 29 0d 20 20 22 52 65 74 | 75 72 6e 20 74 68 65 20 |).  "Ret|urn the |
|000045e0| 6c 65 66 74 6d 6f 73 74 | 20 6e 6f 64 65 20 69 6e |leftmost| node in|
|000045f0| 20 74 68 65 20 74 72 65 | 65 20 72 6f 6f 74 65 64 | the tre|e rooted|
|00004600| 20 61 74 20 6e 6f 64 65 | 22 0d 20 20 28 6f 72 20 | at node|".  (or |
|00004610| 28 62 74 72 65 65 2d 6d | 69 6e 20 6e 6f 64 65 29 |(btree-m|in node)|
|00004620| 0d 20 20 20 20 20 20 6e | 6f 64 65 29 29 0d 0d 28 |.      n|ode))..(|
|00004630| 64 65 66 75 6e 20 6d 61 | 78 2d 76 61 6c 20 28 6e |defun ma|x-val (n|
|00004640| 6f 64 65 29 0d 20 20 22 | 52 65 74 75 72 6e 20 74 |ode).  "|Return t|
|00004650| 68 65 20 6b 65 79 20 61 | 73 73 6f 63 69 61 74 65 |he key a|ssociate|
|00004660| 64 20 77 69 74 68 20 74 | 68 65 20 72 69 67 68 74 |d with t|he right|
|00004670| 6d 6f 73 74 20 6e 6f 64 | 65 20 69 6e 20 74 68 65 |most nod|e in the|
|00004680| 20 74 72 65 65 20 72 6f | 6f 74 65 64 20 61 74 20 | tree ro|oted at |
|00004690| 6e 6f 64 65 22 0d 20 20 | 28 6c 65 74 20 28 28 6d |node".  |(let ((m|
|000046a0| 61 78 2d 6e 6f 64 65 20 | 28 67 65 74 2d 6d 61 78 |ax-node |(get-max|
|000046b0| 20 6e 6f 64 65 29 29 29 | 0d 20 20 20 20 28 62 74 | node)))|.    (bt|
|000046c0| 72 65 65 2d 6b 65 79 20 | 0d 20 20 20 20 20 6d 61 |ree-key |.     ma|
|000046d0| 78 2d 6e 6f 64 65 29 29 | 29 0d 0d 28 64 65 66 75 |x-node))|)..(defu|
|000046e0| 6e 20 6d 69 6e 2d 76 61 | 6c 20 28 6e 6f 64 65 29 |n min-va|l (node)|
|000046f0| 0d 20 20 22 52 65 74 75 | 72 6e 20 74 68 65 20 6b |.  "Retu|rn the k|
|00004700| 65 79 20 61 73 73 6f 63 | 69 61 74 65 64 20 77 69 |ey assoc|iated wi|
|00004710| 74 68 20 74 68 65 20 6c | 65 66 74 6d 6f 73 74 20 |th the l|eftmost |
|00004720| 6e 6f 64 65 20 69 6e 20 | 74 68 65 20 74 72 65 65 |node in |the tree|
|00004730| 20 72 6f 6f 74 65 64 20 | 61 74 20 6e 6f 64 65 22 | rooted |at node"|
|00004740| 0d 20 20 28 6c 65 74 20 | 28 28 6d 69 6e 2d 6e 6f |.  (let |((min-no|
|00004750| 64 65 20 28 67 65 74 2d | 6d 69 6e 20 6e 6f 64 65 |de (get-|min node|
|00004760| 29 29 29 0d 20 20 20 20 | 28 62 74 72 65 65 2d 6b |))).    |(btree-k|
|00004770| 65 79 20 0d 20 20 20 20 | 20 6d 69 6e 2d 6e 6f 64 |ey .    | min-nod|
|00004780| 65 29 29 29 0d 0d 28 64 | 65 66 75 6e 20 70 75 74 |e)))..(d|efun put|
|00004790| 2d 6d 69 6e 2d 6d 61 78 | 20 28 6d 69 6e 2d 6d 61 |-min-max| (min-ma|
|000047a0| 78 20 64 65 66 61 75 6c | 74 20 26 6f 70 74 69 6f |x defaul|t &optio|
|000047b0| 6e 61 6c 20 6f 74 68 65 | 72 29 0d 20 20 22 52 65 |nal othe|r).  "Re|
|000047c0| 74 75 72 6e 73 20 74 68 | 65 20 66 69 72 73 74 20 |turns th|e first |
|000047d0| 6e 6f 6e 2d 6e 75 6c 6c | 20 76 61 6c 75 65 20 69 |non-null| value i|
|000047e0| 6e 20 6d 69 6e 2d 6d 61 | 78 20 64 65 66 61 75 6c |n min-ma|x defaul|
|000047f0| 74 20 6f 74 68 65 72 22 | 20 0d 20 20 28 6f 72 20 |t other"| .  (or |
|00004800| 6d 69 6e 2d 6d 61 78 0d | 20 20 20 20 20 20 64 65 |min-max.|      de|
|00004810| 66 61 75 6c 74 0d 20 20 | 20 20 20 20 6f 74 68 65 |fault.  |    othe|
|00004820| 72 29 29 0d 0d 28 64 65 | 66 75 6e 20 73 65 74 2d |r))..(de|fun set-|
|00004830| 6d 69 6e 2d 6d 61 78 20 | 28 6e 6f 64 65 20 26 6f |min-max |(node &o|
|00004840| 70 74 69 6f 6e 61 6c 20 | 28 64 65 73 63 65 6e 64 |ptional |(descend|
|00004850| 20 30 29 29 0d 20 20 28 | 77 68 65 6e 20 6e 6f 64 | 0)).  (|when nod|
|00004860| 65 0d 20 20 20 20 28 77 | 68 65 6e 20 28 3e 20 64 |e.    (w|hen (> d|
|00004870| 65 73 63 65 6e 64 20 30 | 29 0d 20 20 20 20 20 20 |escend 0|).      |
|00004880| 28 73 65 74 2d 6d 69 6e | 2d 6d 61 78 20 28 62 74 |(set-min|-max (bt|
|00004890| 72 65 65 2d 76 61 6c 20 | 6e 6f 64 65 29 20 28 31 |ree-val |node) (1|
|000048a0| 2d 20 64 65 73 63 65 6e | 64 29 29 29 0d 20 20 20 |- descen|d))).   |
|000048b0| 20 28 69 66 20 28 69 73 | 2d 6c 65 61 66 20 6e 6f | (if (is|-leaf no|
|000048c0| 64 65 29 0d 20 20 20 20 | 20 20 28 76 61 6c 75 65 |de).    |  (value|
|000048d0| 73 20 6e 6f 64 65 20 6e | 6f 64 65 29 0d 20 20 20 |s node n|ode).   |
|000048e0| 20 20 20 28 6c 65 74 20 | 28 28 6d 69 6e 20 28 73 |   (let |((min (s|
|000048f0| 65 74 2d 6d 69 6e 2d 6d | 61 78 20 28 62 74 72 65 |et-min-m|ax (btre|
|00004900| 65 2d 6c 65 66 74 20 6e | 6f 64 65 29 20 64 65 73 |e-left n|ode) des|
|00004910| 63 65 6e 64 29 29 29 0d | 20 20 20 20 20 20 20 20 |cend))).|        |
|00004920| 28 6d 75 6c 74 69 70 6c | 65 2d 76 61 6c 75 65 2d |(multipl|e-value-|
|00004930| 62 69 6e 64 20 28 6d 69 | 6e 72 20 6d 61 78 29 0d |bind (mi|nr max).|
|00004940| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00004950| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 28 73 65 |        |     (se|
|00004960| 74 2d 6d 69 6e 2d 6d 61 | 78 20 28 62 74 72 65 65 |t-min-ma|x (btree|
|00004970| 2d 72 69 67 68 74 20 6e | 6f 64 65 29 20 64 65 73 |-right n|ode) des|
|00004980| 63 65 6e 64 29 0d 20 20 | 20 20 20 20 20 20 20 20 |cend).  |        |
|00004990| 28 64 65 63 6c 61 72 65 | 20 28 69 67 6e 6f 72 65 |(declare| (ignore|
|000049a0| 20 6d 69 6e 72 29 29 0d | 20 20 20 20 20 20 20 20 | minr)).|        |
|000049b0| 20 20 28 73 65 74 66 20 | 28 62 74 72 65 65 2d 6d |  (setf |(btree-m|
|000049c0| 69 6e 20 6e 6f 64 65 29 | 20 6d 69 6e 0d 20 20 20 |in node)| min.   |
|000049d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 28 62 74 |        |     (bt|
|000049e0| 72 65 65 2d 6d 61 78 20 | 6e 6f 64 65 29 20 6d 61 |ree-max |node) ma|
|000049f0| 78 29 0d 20 20 20 20 20 | 20 20 20 20 20 28 76 61 |x).     |     (va|
|00004a00| 6c 75 65 73 20 6d 69 6e | 20 6d 61 78 29 29 29 29 |lues min| max))))|
|00004a10| 29 29 0d 0d 28 64 65 66 | 75 6e 20 73 75 70 70 6c |))..(def|un suppl|
|00004a20| 79 2d 6d 69 6e 2f 6d 61 | 78 20 28 70 61 72 65 6e |y-min/ma|x (paren|
|00004a30| 74 20 63 68 69 6c 64 29 | 0d 20 20 22 49 66 20 63 |t child)|.  "If c|
|00004a40| 68 69 6c 64 20 69 73 20 | 74 68 65 20 6c 65 66 74 |hild is |the left|
|00004a50| 2f 72 69 67 68 74 20 6e | 6f 64 65 20 6f 66 20 74 |/right n|ode of t|
|00004a60| 68 65 20 70 61 72 65 6e | 74 2c 20 72 65 74 75 72 |he paren|t, retur|
|00004a70| 6e 73 20 74 68 65 20 6e | 6f 64 65 3b 0d 6f 74 68 |ns the n|ode;.oth|
|00004a80| 65 72 77 69 73 65 20 72 | 65 74 75 72 6e 73 20 74 |erwise r|eturns t|
|00004a90| 68 65 20 70 61 72 65 6e | 74 22 0d 20 20 28 69 66 |he paren|t".  (if|
|00004aa0| 20 63 68 69 6c 64 0d 20 | 20 20 20 63 68 69 6c 64 | child. |   child|
|00004ab0| 0d 20 20 20 20 70 61 72 | 65 6e 74 29 29 0d 0d 28 |.    par|ent))..(|
|00004ac0| 64 65 66 75 6e 20 66 69 | 78 2d 6d 61 78 2d 6d 69 |defun fi|x-max-mi|
|00004ad0| 6e 20 28 6e 6f 64 65 29 | 0d 20 20 22 45 6e 73 75 |n (node)|.  "Ensu|
|00004ae0| 72 65 73 20 74 68 61 74 | 20 74 68 65 20 6e 6f 64 |res that| the nod|
|00004af0| 65 20 68 61 73 20 74 68 | 65 20 70 72 6f 70 65 72 |e has th|e proper|
|00004b00| 20 6d 69 6e 20 61 6e 64 | 20 6d 61 78 20 6c 69 6e | min and| max lin|
|00004b10| 6b 73 20 61 6e 64 20 74 | 68 61 74 0d 74 68 65 20 |ks and t|hat.the |
|00004b20| 6c 65 66 74 20 61 6e 64 | 20 72 69 67 68 74 20 63 |left and| right c|
|00004b30| 68 69 6c 64 72 65 6e 20 | 61 72 65 20 66 69 78 65 |hildren |are fixe|
|00004b40| 64 20 69 66 20 74 68 65 | 79 20 61 72 65 20 6c 65 |d if the|y are le|
|00004b50| 61 76 65 73 2e 22 0d 20 | 20 28 6c 65 74 20 28 6c |aves.". | (let (l|
|00004b60| 65 66 74 20 72 69 67 68 | 74 29 0d 20 20 20 20 28 |eft righ|t).    (|
|00004b70| 77 68 65 6e 20 6e 6f 64 | 65 0d 20 20 20 20 20 20 |when nod|e.      |
|00004b80| 28 73 65 74 71 20 6c 65 | 66 74 20 28 62 74 72 65 |(setq le|ft (btre|
|00004b90| 65 2d 6c 65 66 74 20 6e | 6f 64 65 29 0d 20 20 20 |e-left n|ode).   |
|00004ba0| 20 20 20 20 20 20 20 20 | 20 72 69 67 68 74 20 28 |        | right (|
|00004bb0| 62 74 72 65 65 2d 72 69 | 67 68 74 20 6e 6f 64 65 |btree-ri|ght node|
|00004bc0| 29 29 0d 20 20 20 20 20 | 20 28 63 68 65 63 6b 2d |)).     | (check-|
|00004bd0| 6c 65 61 66 20 6c 65 66 | 74 29 0d 20 20 20 20 20 |leaf lef|t).     |
|00004be0| 20 28 63 68 65 63 6b 2d | 6c 65 61 66 20 72 69 67 | (check-|leaf rig|
|00004bf0| 68 74 29 0d 20 20 20 20 | 20 20 28 73 65 74 66 20 |ht).    |  (setf |
|00004c00| 28 62 74 72 65 65 2d 6d | 69 6e 20 6e 6f 64 65 29 |(btree-m|in node)|
|00004c10| 20 28 70 75 74 2d 6d 69 | 6e 2d 6d 61 78 20 28 67 | (put-mi|n-max (g|
|00004c20| 65 74 2d 6d 69 6e 20 6c | 65 66 74 29 20 6c 65 66 |et-min l|eft) lef|
|00004c30| 74 29 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 28 |t).     |       (|
|00004c40| 62 74 72 65 65 2d 6d 61 | 78 20 6e 6f 64 65 29 20 |btree-ma|x node) |
|00004c50| 28 70 75 74 2d 6d 69 6e | 2d 6d 61 78 20 28 67 65 |(put-min|-max (ge|
|00004c60| 74 2d 6d 61 78 20 72 69 | 67 68 74 29 20 72 69 67 |t-max ri|ght) rig|
|00004c70| 68 74 29 29 0d 20 20 20 | 20 20 20 28 77 68 65 6e |ht)).   |   (when|
|00004c80| 20 28 69 73 2d 64 65 62 | 75 67 29 20 0d 20 20 20 | (is-deb|ug) .   |
|00004c90| 20 20 20 20 20 28 70 72 | 69 6e 74 2d 64 62 20 28 |     (pr|int-db (|
|00004ca0| 62 74 72 65 65 2d 6b 65 | 79 20 6e 6f 64 65 29 20 |btree-ke|y node) |
|00004cb0| 28 6d 69 6e 2d 76 61 6c | 20 6e 6f 64 65 29 20 28 |(min-val| node) (|
|00004cc0| 6d 61 78 2d 76 61 6c 20 | 6e 6f 64 65 29 29 29 29 |max-val |node))))|
|00004cd0| 29 29 0d 0d 28 64 65 66 | 75 6e 20 71 2d 61 64 6a |))..(def|un q-adj|
|00004ce0| 75 73 74 2d 6d 61 78 20 | 28 70 61 74 68 29 0d 20 |ust-max |(path). |
|00004cf0| 20 22 41 64 6a 75 73 74 | 73 20 61 20 70 61 74 68 | "Adjust|s a path|
|00004d00| 20 6f 66 20 74 68 65 20 | 66 6f 72 6d 20 28 64 69 | of the |form (di|
|00004d10| 72 20 6e 6f 64 65 29 20 | 2e 2e 2e 20 28 64 69 72 |r node) |... (dir|
|00004d20| 20 6e 6f 64 65 29 0d 73 | 65 74 74 69 6e 67 20 74 | node).s|etting t|
|00004d30| 68 65 20 6d 61 78 20 20 | 6c 69 6e 6b 73 20 61 70 |he max  |links ap|
|00004d40| 70 72 6f 70 72 69 61 74 | 65 6c 79 20 20 66 6f 72 |propriat|ely  for|
|00004d50| 20 65 61 63 68 20 6e 6f | 64 65 20 66 6f 72 20 61 | each no|de for a|
|00004d60| 6c 6c 20 72 69 67 68 74 | 20 74 75 72 6e 73 22 0d |ll right| turns".|
|00004d70| 20 20 28 6c 65 74 20 28 | 6e 65 77 2d 6d 61 78 29 |  (let (|new-max)|
|00004d80| 0d 20 20 20 20 28 77 68 | 65 6e 20 70 61 74 68 0d |.    (wh|en path.|
|00004d90| 20 20 20 20 20 20 28 73 | 65 74 71 20 6e 65 77 2d |      (s|etq new-|
|00004da0| 6d 61 78 20 28 67 65 74 | 2d 6d 61 78 20 28 62 74 |max (get|-max (bt|
|00004db0| 72 61 69 6c 2d 6e 6f 64 | 65 20 28 66 69 72 73 74 |rail-nod|e (first|
|00004dc0| 20 70 61 74 68 29 29 29 | 29 29 0d 20 20 20 20 28 | path)))|)).    (|
|00004dd0| 6c 6f 6f 70 20 66 6f 72 | 20 74 65 6d 70 20 69 6e |loop for| temp in|
|00004de0| 20 28 72 65 73 74 20 70 | 61 74 68 29 0d 20 20 20 | (rest p|ath).   |
|00004df0| 20 20 20 20 20 20 20 77 | 69 74 68 20 64 69 72 20 |       w|ith dir |
|00004e00| 61 6e 64 20 6e 6f 64 65 | 0d 20 20 20 20 20 20 20 |and node|.       |
|00004e10| 20 20 20 64 6f 20 28 73 | 65 74 71 20 64 69 72 20 |   do (s|etq dir |
|00004e20| 28 62 74 72 61 69 6c 2d | 64 69 72 20 74 65 6d 70 |(btrail-|dir temp|
|00004e30| 29 20 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |) .     |        |
|00004e40| 20 20 20 20 20 20 6e 6f | 64 65 20 28 62 74 72 61 |      no|de (btra|
|00004e50| 69 6c 2d 6e 6f 64 65 20 | 74 65 6d 70 29 29 0d 20 |il-node |temp)). |
|00004e60| 20 20 20 20 20 20 20 20 | 20 75 6e 74 69 6c 20 28 |        | until (|
|00004e70| 65 71 75 61 6c 20 64 69 | 72 20 2a 6c 65 66 74 2a |equal di|r *left*|
|00004e80| 29 0d 20 20 20 20 20 20 | 20 20 20 20 64 6f 20 28 |).      |    do (|
|00004e90| 73 65 74 66 20 28 62 74 | 72 65 65 2d 6d 61 78 20 |setf (bt|ree-max |
|00004ea0| 6e 6f 64 65 29 0d 20 20 | 20 20 20 20 20 20 20 20 |node).  |        |
|00004eb0| 20 20 20 20 20 20 20 20 | 20 28 75 6e 6c 65 73 73 |        | (unless|
|00004ec0| 20 28 65 71 20 6e 65 77 | 2d 6d 61 78 20 6e 6f 64 | (eq new|-max nod|
|00004ed0| 65 29 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |e).     |        |
|00004ee0| 20 20 20 20 20 20 20 20 | 6e 65 77 2d 6d 61 78 29 |        |new-max)|
|00004ef0| 29 29 29 29 0d 0d 28 64 | 65 66 75 6e 20 71 2d 61 |))))..(d|efun q-a|
|00004f00| 64 6a 75 73 74 2d 6d 61 | 78 2d 6d 69 6e 20 28 70 |djust-ma|x-min (p|
|00004f10| 61 74 68 29 0d 20 20 22 | 41 64 6a 75 73 74 73 20 |ath).  "|Adjusts |
|00004f20| 61 20 70 61 74 68 20 6f | 66 20 74 68 65 20 66 6f |a path o|f the fo|
|00004f30| 72 6d 20 28 64 69 72 20 | 6e 6f 64 65 29 20 2e 2e |rm (dir |node) ..|
|00004f40| 2e 20 28 64 69 72 20 6e | 6f 64 65 29 0d 73 65 74 |. (dir n|ode).set|
|00004f50| 74 69 6e 67 20 74 68 65 | 20 6d 61 78 20 28 61 6e |ting the| max (an|
|00004f60| 64 20 6d 69 6e 29 20 6c | 69 6e 6b 73 20 61 70 70 |d min) l|inks app|
|00004f70| 72 6f 70 72 69 61 74 65 | 6c 79 20 66 6f 72 20 65 |ropriate|ly for e|
|00004f80| 61 63 68 20 6e 6f 64 65 | 20 66 6f 72 20 61 6c 6c |ach node| for all|
|00004f90| 20 72 69 67 68 74 20 28 | 61 6e 64 20 6c 65 66 74 | right (|and left|
|00004fa0| 29 20 74 75 72 6e 73 22 | 0d 20 20 28 71 2d 61 64 |) turns"|.  (q-ad|
|00004fb0| 6a 75 73 74 2d 6d 61 78 | 20 70 61 74 68 29 0d 20 |just-max| path). |
|00004fc0| 20 28 71 2d 61 64 6a 75 | 73 74 2d 6d 69 6e 20 70 | (q-adju|st-min p|
|00004fd0| 61 74 68 29 29 0d 0d 28 | 64 65 66 75 6e 20 71 2d |ath))..(|defun q-|
|00004fe0| 61 64 6a 75 73 74 2d 6d | 69 6e 20 28 70 61 74 68 |adjust-m|in (path|
|00004ff0| 29 0d 20 20 22 41 64 6a | 75 73 74 73 20 61 20 70 |).  "Adj|usts a p|
|00005000| 61 74 68 20 6f 66 20 74 | 68 65 20 66 6f 72 6d 20 |ath of t|he form |
|00005010| 28 64 69 72 20 6e 6f 64 | 65 29 20 2e 2e 2e 20 28 |(dir nod|e) ... (|
|00005020| 64 69 72 20 6e 6f 64 65 | 29 0d 73 65 74 74 69 6e |dir node|).settin|
|00005030| 67 20 74 68 65 20 6d 69 | 6e 20 6c 69 6e 6b 73 20 |g the mi|n links |
|00005040| 61 70 70 72 6f 70 72 69 | 61 74 65 6c 79 20 66 6f |appropri|ately fo|
|00005050| 72 20 61 6c 6c 20 6c 65 | 66 74 20 74 75 72 6e 73 |r all le|ft turns|
|00005060| 22 0d 20 20 28 6c 65 74 | 20 28 6e 65 77 2d 6d 69 |".  (let| (new-mi|
|00005070| 6e 29 0d 20 20 20 20 28 | 77 68 65 6e 20 70 61 74 |n).    (|when pat|
|00005080| 68 0d 20 20 20 20 20 20 | 28 73 65 74 71 20 6e 65 |h.      |(setq ne|
|00005090| 77 2d 6d 69 6e 20 28 67 | 65 74 2d 6d 69 6e 20 28 |w-min (g|et-min (|
|000050a0| 62 74 72 61 69 6c 2d 6e | 6f 64 65 20 28 66 69 72 |btrail-n|ode (fir|
|000050b0| 73 74 20 70 61 74 68 29 | 29 29 29 29 0d 20 20 20 |st path)|)))).   |
|000050c0| 20 28 6c 6f 6f 70 20 66 | 6f 72 20 74 65 6d 70 20 | (loop f|or temp |
|000050d0| 69 6e 20 28 72 65 73 74 | 20 70 61 74 68 29 0d 20 |in (rest| path). |
|000050e0| 20 20 20 20 20 20 20 20 | 20 77 69 74 68 20 64 69 |        | with di|
|000050f0| 72 20 61 6e 64 20 6e 6f | 64 65 0d 20 20 20 20 20 |r and no|de.     |
|00005100| 20 20 20 20 20 64 6f 20 | 28 73 65 74 71 20 64 69 |     do |(setq di|
|00005110| 72 20 28 62 74 72 61 69 | 6c 2d 64 69 72 20 74 65 |r (btrai|l-dir te|
|00005120| 6d 70 29 20 0d 20 20 20 | 20 20 20 20 20 20 20 20 |mp) .   |        |
|00005130| 20 20 20 20 20 20 20 20 | 6e 6f 64 65 20 28 62 74 |        |node (bt|
|00005140| 72 61 69 6c 2d 6e 6f 64 | 65 20 74 65 6d 70 29 29 |rail-nod|e temp))|
|00005150| 0d 20 20 20 20 20 20 20 | 20 20 20 75 6e 74 69 6c |.       |   until|
|00005160| 20 28 65 71 75 61 6c 20 | 64 69 72 20 2a 72 69 67 | (equal |dir *rig|
|00005170| 68 74 2a 29 0d 20 20 20 | 20 20 20 20 20 20 20 64 |ht*).   |       d|
|00005180| 6f 20 28 73 65 74 66 20 | 28 62 74 72 65 65 2d 6d |o (setf |(btree-m|
|00005190| 69 6e 20 6e 6f 64 65 29 | 0d 20 20 20 20 20 20 20 |in node)|.       |
|000051a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 28 75 6e 6c |        |    (unl|
|000051b0| 65 73 73 20 28 65 71 20 | 6e 65 77 2d 6d 69 6e 20 |ess (eq |new-min |
|000051c0| 6e 6f 64 65 29 0d 20 20 | 20 20 20 20 20 20 20 20 |node).  |        |
|000051d0| 20 20 20 20 20 20 20 20 | 20 20 20 6e 65 77 2d 6d |        |   new-m|
|000051e0| 69 6e 29 29 29 29 29 0d | 0d 28 64 65 66 75 6e 20 |in))))).|.(defun |
|000051f0| 61 64 6a 75 73 74 2d 6d | 61 78 20 28 6e 65 77 2d |adjust-m|ax (new-|
|00005200| 6d 61 78 20 70 61 74 68 | 29 0d 20 20 22 41 64 6a |max path|).  "Adj|
|00005210| 75 73 74 73 20 61 20 70 | 61 74 68 20 6f 66 20 74 |usts a p|ath of t|
|00005220| 68 65 20 66 6f 72 6d 20 | 28 64 69 72 20 6e 6f 64 |he form |(dir nod|
|00005230| 65 29 20 2e 2e 2e 20 28 | 64 69 72 20 6e 6f 64 65 |e) ... (|dir node|
|00005240| 29 0d 73 65 74 74 69 6e | 67 20 74 68 65 20 6d 61 |).settin|g the ma|
|00005250| 78 20 6c 69 6e 6b 73 20 | 61 70 70 72 6f 70 72 69 |x links |appropri|
|00005260| 61 74 65 6c 79 20 66 6f | 72 20 65 61 63 68 20 6e |ately fo|r each n|
|00005270| 6f 64 65 20 66 6f 72 20 | 61 6c 6c 20 72 69 67 68 |ode for |all righ|
|00005280| 74 20 74 75 72 6e 73 22 | 0d 20 20 28 6c 6f 6f 70 |t turns"|.  (loop|
|00005290| 20 66 6f 72 20 74 65 6d | 70 20 69 6e 20 70 61 74 | for tem|p in pat|
|000052a0| 68 20 0d 20 20 20 20 20 | 20 20 20 77 69 74 68 20 |h .     |   with |
|000052b0| 64 69 72 20 61 6e 64 20 | 6e 6f 64 65 0d 20 20 20 |dir and |node.   |
|000052c0| 20 20 20 20 20 64 6f 20 | 28 73 65 74 71 20 64 69 |     do |(setq di|
|000052d0| 72 20 28 62 74 72 61 69 | 6c 2d 64 69 72 20 74 65 |r (btrai|l-dir te|
|000052e0| 6d 70 29 20 0d 20 20 20 | 20 20 20 20 20 20 20 20 |mp) .   |        |
|000052f0| 20 20 20 20 20 20 6e 6f | 64 65 20 28 62 74 72 61 |      no|de (btra|
|00005300| 69 6c 2d 6e 6f 64 65 20 | 74 65 6d 70 29 29 0d 20 |il-node |temp)). |
|00005310| 20 20 20 20 20 20 20 75 | 6e 74 69 6c 20 28 65 71 |       u|ntil (eq|
|00005320| 75 61 6c 20 64 69 72 20 | 2a 6c 65 66 74 2a 29 0d |ual dir |*left*).|
|00005330| 20 20 20 20 20 20 20 20 | 64 6f 20 28 73 65 74 66 |        |do (setf|
|00005340| 20 28 62 74 72 65 65 2d | 6d 61 78 20 6e 6f 64 65 | (btree-|max node|
|00005350| 29 0d 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |).      |        |
|00005360| 20 20 20 28 75 6e 6c 65 | 73 73 20 28 65 71 20 6e |   (unle|ss (eq n|
|00005370| 65 77 2d 6d 61 78 20 6e | 6f 64 65 29 0d 20 20 20 |ew-max n|ode).   |
|00005380| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00005390| 6e 65 77 2d 6d 61 78 29 | 29 29 29 0d 0d 28 64 65 |new-max)|)))..(de|
|000053a0| 66 75 6e 20 61 64 6a 75 | 73 74 2d 6d 69 6e 20 28 |fun adju|st-min (|
|000053b0| 6e 65 77 2d 6d 69 6e 20 | 70 61 74 68 29 0d 20 20 |new-min |path).  |
|000053c0| 28 6c 65 74 20 28 6e 6f | 64 65 29 0d 20 20 20 20 |(let (no|de).    |
|000053d0| 28 64 6f 6c 69 73 74 20 | 28 74 65 6d 70 20 70 61 |(dolist |(temp pa|
|000053e0| 74 68 29 0d 20 20 20 20 | 20 20 28 73 65 74 66 20 |th).    |  (setf |
|000053f0| 6e 6f 64 65 20 28 62 74 | 72 61 69 6c 2d 6e 6f 64 |node (bt|rail-nod|
|00005400| 65 20 74 65 6d 70 29 29 | 0d 20 20 20 20 20 20 28 |e temp))|.      (|
|00005410| 69 66 20 28 65 71 20 6e | 6f 64 65 20 6e 65 77 2d |if (eq n|ode new-|
|00005420| 6d 69 6e 29 0d 20 20 20 | 20 20 20 20 20 28 73 65 |min).   |     (se|
|00005430| 74 66 20 28 62 74 72 65 | 65 2d 6d 69 6e 20 6e 6f |tf (btre|e-min no|
|00005440| 64 65 29 20 6e 69 6c 29 | 0d 20 20 20 20 20 20 20 |de) nil)|.       |
|00005450| 20 28 73 65 6c 65 63 74 | 20 28 62 74 72 61 69 6c | (select| (btrail|
|00005460| 2d 64 69 72 20 74 65 6d | 70 29 0d 20 20 20 20 20 |-dir tem|p).     |
|00005470| 20 20 20 20 20 28 2a 65 | 71 75 61 6c 2a 20 28 73 |     (*e|qual* (s|
|00005480| 65 74 66 20 28 62 74 72 | 65 65 2d 6d 69 6e 20 6e |etf (btr|ee-min n|
|00005490| 6f 64 65 29 20 6e 69 6c | 29 29 0d 20 20 20 20 20 |ode) nil|)).     |
|000054a0| 20 20 20 20 20 28 2a 72 | 69 67 68 74 2a 20 28 72 |     (*r|ight* (r|
|000054b0| 65 74 75 72 6e 20 74 29 | 29 0d 20 20 20 20 20 20 |eturn t)|).      |
|000054c0| 20 20 20 20 28 2a 6c 65 | 66 74 2a 0d 20 20 20 20 |    (*le|ft*.    |
|000054d0| 20 20 20 20 20 20 20 28 | 73 65 74 66 20 28 62 74 |       (|setf (bt|
|000054e0| 72 65 65 2d 6d 69 6e 20 | 6e 6f 64 65 29 0d 20 20 |ree-min |node).  |
|000054f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 28 |        |       (|
|00005500| 69 66 20 28 65 71 20 6e | 65 77 2d 6d 69 6e 20 6e |if (eq n|ew-min n|
|00005510| 6f 64 65 29 0d 20 20 20 | 20 20 20 20 20 20 20 20 |ode).   |        |
|00005520| 20 20 20 20 20 20 20 20 | 6e 69 6c 0d 20 20 20 20 |        |nil.    |
|00005530| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 6e |        |       n|
|00005540| 65 77 2d 6d 69 6e 29 29 | 29 29 29 29 29 29 0d 0d |ew-min))|))))))..|
|00005550| 3b 3b 20 2d 2d 3e 20 74 | 75 72 6e 20 72 6f 75 74 |;; --> t|urn rout|
|00005560| 69 6e 65 73 0d 0d 28 64 | 65 66 75 6e 20 65 78 74 |ines..(d|efun ext|
|00005570| 72 65 6d 65 2d 74 75 72 | 6e 20 28 70 61 74 68 20 |reme-tur|n (path |
|00005580| 64 69 72 29 0d 20 20 22 | 63 6f 6e 74 69 6e 75 65 |dir).  "|continue|
|00005590| 20 74 75 72 6e 69 6e 67 | 20 69 6e 20 74 68 65 20 | turning| in the |
|000055a0| 64 69 72 65 63 74 69 6f | 6e 20 64 69 72 20 66 72 |directio|n dir fr|
|000055b0| 6f 6d 20 74 68 65 20 6c | 61 73 74 20 6e 6f 64 65 |om the l|ast node|
|000055c0| 20 69 6e 20 70 61 74 68 | 20 0d 75 6e 74 69 6c 20 | in path| .until |
|000055d0| 6e 6f 20 6d 6f 72 65 20 | 64 69 72 20 74 75 72 6e |no more |dir turn|
|000055e0| 73 20 61 72 65 20 70 6f | 73 73 69 62 6c 65 22 0d |s are po|ssible".|
|000055f0| 20 20 28 6c 65 74 20 28 | 74 65 6d 70 20 6e 6f 64 |  (let (|temp nod|
|00005600| 65 20 6f 6c 64 2d 70 61 | 74 68 29 0d 20 20 20 20 |e old-pa|th).    |
|00005610| 28 6c 6f 6f 70 0d 20 20 | 20 20 20 20 28 73 65 74 |(loop.  |    (set|
|00005620| 66 20 74 65 6d 70 20 28 | 66 69 72 73 74 20 70 61 |f temp (|first pa|
|00005630| 74 68 29 0d 20 20 20 20 | 20 20 20 20 20 20 20 20 |th).    |        |
|00005640| 6e 6f 64 65 20 28 62 74 | 72 61 69 6c 2d 6e 6f 64 |node (bt|rail-nod|
|00005650| 65 20 74 65 6d 70 29 29 | 0d 20 20 20 20 20 20 28 |e temp))|.      (|
|00005660| 77 68 65 6e 20 28 6f 72 | 20 28 69 73 2d 6c 65 61 |when (or| (is-lea|
|00005670| 66 20 6e 6f 64 65 29 20 | 28 65 71 20 70 61 74 68 |f node) |(eq path|
|00005680| 20 6f 6c 64 2d 70 61 74 | 68 29 29 0d 20 20 20 20 | old-pat|h)).    |
|00005690| 20 20 20 20 28 72 65 74 | 75 72 6e 20 70 61 74 68 |    (ret|urn path|
|000056a0| 29 29 0d 20 20 20 20 20 | 20 28 73 65 74 66 20 6f |)).     | (setf o|
|000056b0| 6c 64 2d 70 61 74 68 20 | 70 61 74 68 0d 20 20 20 |ld-path |path.   |
|000056c0| 20 20 20 20 20 20 20 20 | 20 70 61 74 68 20 28 74 |        | path (t|
|000056d0| 75 72 6e 2d 69 6d 6d 65 | 64 69 61 74 65 20 70 61 |urn-imme|diate pa|
|000056e0| 74 68 20 64 69 72 29 29 | 29 29 29 0d 0d 28 64 65 |th dir))|)))..(de|
|000056f0| 66 75 6e 20 65 78 74 72 | 65 6d 65 2d 6c 65 66 74 |fun extr|eme-left|
|00005700| 20 28 70 61 74 68 29 0d | 20 20 22 63 6f 6e 74 69 | (path).|  "conti|
|00005710| 6e 75 65 20 74 75 72 6e | 69 6e 67 20 6c 65 66 74 |nue turn|ing left|
|00005720| 20 66 72 6f 6d 20 74 68 | 65 20 6c 61 73 74 20 6e | from th|e last n|
|00005730| 6f 64 65 20 69 6e 20 70 | 61 74 68 20 0d 75 6e 74 |ode in p|ath .unt|
|00005740| 69 6c 20 6e 6f 20 6d 6f | 72 65 20 6c 65 66 74 20 |il no mo|re left |
|00005750| 74 75 72 6e 73 20 61 72 | 65 20 70 6f 73 73 69 62 |turns ar|e possib|
|00005760| 6c 65 22 0d 20 20 28 65 | 78 74 72 65 6d 65 2d 74 |le".  (e|xtreme-t|
|00005770| 75 72 6e 20 70 61 74 68 | 20 2a 6c 65 66 74 2a 29 |urn path| *left*)|
|00005780| 29 0d 0d 28 64 65 66 75 | 6e 20 65 78 74 72 65 6d |)..(defu|n extrem|
|00005790| 65 2d 72 69 67 68 74 20 | 28 70 61 74 68 29 0d 20 |e-right |(path). |
|000057a0| 20 22 63 6f 6e 74 69 6e | 75 65 20 74 75 72 6e 69 | "contin|ue turni|
|000057b0| 6e 67 20 72 69 67 68 74 | 20 66 72 6f 6d 20 74 68 |ng right| from th|
|000057c0| 65 20 6c 61 73 74 20 6e | 6f 64 65 20 69 6e 20 70 |e last n|ode in p|
|000057d0| 61 74 68 20 0d 75 6e 74 | 69 6c 20 6e 6f 20 6d 6f |ath .unt|il no mo|
|000057e0| 72 65 20 72 69 67 68 74 | 20 74 75 72 6e 73 20 61 |re right| turns a|
|000057f0| 72 65 20 70 6f 73 73 69 | 62 6c 65 22 0d 20 20 28 |re possi|ble".  (|
|00005800| 65 78 74 72 65 6d 65 2d | 74 75 72 6e 20 70 61 74 |extreme-|turn pat|
|00005810| 68 20 2a 72 69 67 68 74 | 2a 29 29 0d 0d 28 64 65 |h *right|*))..(de|
|00005820| 66 75 6e 20 74 75 72 6e | 20 28 70 61 74 68 20 64 |fun turn| (path d|
|00005830| 69 72 29 0d 20 20 22 54 | 75 72 6e 20 69 6e 20 74 |ir).  "T|urn in t|
|00005840| 68 65 20 64 69 72 65 63 | 74 69 6f 6e 20 64 69 72 |he direc|tion dir|
|00005850| 20 66 72 6f 6d 20 74 68 | 65 20 6c 61 73 74 20 6e | from th|e last n|
|00005860| 6f 64 65 20 69 6e 20 74 | 68 65 20 70 61 74 68 22 |ode in t|he path"|
|00005870| 0d 20 20 28 6c 65 74 20 | 28 74 65 6d 70 0d 20 20 |.  (let |(temp.  |
|00005880| 20 20 20 20 20 20 6f 6c | 64 2d 64 69 72 0d 20 20 |      ol|d-dir.  |
|00005890| 20 20 20 20 20 20 6e 65 | 77 2d 6e 6f 64 65 0d 20 |      ne|w-node. |
|000058a0| 20 20 20 20 20 20 20 6e | 6f 64 65 20 0d 20 20 20 |       n|ode .   |
|000058b0| 20 20 20 20 20 28 6f 6c | 64 2d 70 61 74 68 20 70 |     (ol|d-path p|
|000058c0| 61 74 68 29 29 0d 20 20 | 20 20 28 6c 6f 6f 70 0d |ath)).  |  (loop.|
|000058d0| 20 20 20 20 20 20 28 75 | 6e 6c 65 73 73 20 70 61 |      (u|nless pa|
|000058e0| 74 68 0d 20 20 20 20 20 | 20 20 20 28 72 65 74 75 |th.     |   (retu|
|000058f0| 72 6e 20 6f 6c 64 2d 70 | 61 74 68 29 29 0d 20 20 |rn old-p|ath)).  |
|00005900| 20 20 20 20 28 73 65 74 | 66 20 74 65 6d 70 20 28 |    (set|f temp (|
|00005910| 66 69 72 73 74 20 70 61 | 74 68 29 0d 20 20 20 20 |first pa|th).    |
|00005920| 20 20 20 20 20 20 20 20 | 6f 6c 64 2d 64 69 72 20 |        |old-dir |
|00005930| 28 62 74 72 61 69 6c 2d | 64 69 72 20 74 65 6d 70 |(btrail-|dir temp|
|00005940| 29 0d 20 20 20 20 20 20 | 20 20 20 20 20 20 6e 6f |).      |      no|
|00005950| 64 65 20 28 62 74 72 61 | 69 6c 2d 6e 6f 64 65 20 |de (btra|il-node |
|00005960| 74 65 6d 70 29 0d 20 20 | 20 20 20 20 20 20 20 20 |temp).  |        |
|00005970| 20 20 6e 65 77 2d 6e 6f | 64 65 20 28 73 65 6c 65 |  new-no|de (sele|
|00005980| 63 74 20 6f 6c 64 2d 64 | 69 72 0d 20 20 20 20 20 |ct old-d|ir.     |
|00005990| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000059a0| 20 20 28 2a 65 71 75 61 | 6c 2a 20 28 74 75 72 6e |  (*equa|l* (turn|
|000059b0| 31 20 6e 6f 64 65 20 64 | 69 72 29 29 20 3b 20 68 |1 node d|ir)) ; h|
|000059c0| 61 76 65 6e 27 74 20 61 | 6c 72 65 61 64 79 20 74 |aven't a|lready t|
|000059d0| 75 72 6e 65 64 20 6c 65 | 66 74 20 6f 72 20 72 69 |urned le|ft or ri|
|000059e0| 67 68 74 0d 20 20 20 20 | 20 20 20 20 20 20 20 20 |ght.    |        |
|000059f0| 20 20 20 20 20 20 20 20 | 20 20 20 28 2a 62 65 66 |        |   (*bef|
|00005a00| 6f 72 65 2a 20 0d 20 20 | 20 20 20 20 20 20 20 20 |ore* .  |        |
|00005a10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 28 77 |        |      (w|
|00005a20| 68 65 6e 20 28 3d 20 64 | 69 72 20 2a 72 69 67 68 |hen (= d|ir *righ|
|00005a30| 74 2a 29 20 3b 20 68 61 | 76 65 6e 27 74 20 61 6c |t*) ; ha|ven't al|
|00005a40| 72 65 61 64 79 20 74 75 | 72 6e 65 64 20 72 69 67 |ready tu|rned rig|
|00005a50| 68 74 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |ht.     |        |
|00005a60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 28 74 75 |        |     (tu|
|00005a70| 72 6e 31 20 6e 6f 64 65 | 20 64 69 72 29 29 29 29 |rn1 node| dir))))|
|00005a80| 29 0d 20 20 20 20 20 20 | 28 77 68 65 6e 20 6e 65 |).      |(when ne|
|00005a90| 77 2d 6e 6f 64 65 0d 20 | 20 20 20 20 20 20 20 28 |w-node. |       (|
|00005aa0| 73 65 74 66 20 28 62 74 | 72 61 69 6c 2d 64 69 72 |setf (bt|rail-dir|
|00005ab0| 20 74 65 6d 70 29 20 64 | 69 72 29 0d 20 20 20 20 | temp) d|ir).    |
|00005ac0| 20 20 20 20 28 66 6f 75 | 6e 64 2d 6e 6f 64 65 20 |    (fou|nd-node |
|00005ad0| 6e 65 77 2d 6e 6f 64 65 | 20 70 61 74 68 29 0d 20 |new-node| path). |
|00005ae0| 20 20 20 20 20 20 20 28 | 72 65 74 75 72 6e 20 70 |       (|return p|
|00005af0| 61 74 68 29 29 0d 20 20 | 20 20 20 20 28 70 6f 70 |ath)).  |    (pop|
|00005b00| 20 70 61 74 68 29 29 29 | 29 0d 0d 28 64 65 66 75 | path)))|)..(defu|
|00005b10| 6e 20 74 75 72 6e 2d 69 | 6d 6d 65 64 69 61 74 65 |n turn-i|mmediate|
|00005b20| 20 28 70 61 74 68 20 64 | 69 72 29 0d 20 20 22 4d | (path d|ir).  "M|
|00005b30| 61 6b 65 20 61 20 64 69 | 72 20 28 6c 65 66 74 2f |ake a di|r (left/|
|00005b40| 72 69 67 68 74 29 20 74 | 75 72 6e 20 66 72 6f 6d |right) t|urn from|
|00005b50| 20 74 68 65 20 6c 61 73 | 74 20 6e 6f 64 65 20 69 | the las|t node i|
|00005b60| 6e 20 70 61 74 68 22 0d | 20 20 28 6c 65 74 2a 20 |n path".|  (let* |
|00005b70| 28 28 74 65 6d 70 20 28 | 66 69 72 73 74 20 70 61 |((temp (|first pa|
|00005b80| 74 68 29 29 0d 20 20 20 | 20 20 20 20 20 20 28 6e |th)).   |      (n|
|00005b90| 6f 64 65 20 28 62 74 72 | 61 69 6c 2d 6e 6f 64 65 |ode (btr|ail-node|
|00005ba0| 20 74 65 6d 70 29 29 0d | 20 20 20 20 20 20 20 20 | temp)).|        |
|00005bb0| 20 6e 65 77 2d 6e 6f 64 | 65 29 0d 20 20 20 20 3b | new-nod|e).    ;|
|00005bc0| 20 77 68 65 6e 20 74 68 | 65 20 6e 6f 64 65 20 69 | when th|e node i|
|00005bd0| 73 20 6e 6f 74 20 61 20 | 6c 65 61 66 20 61 6e 64 |s not a |leaf and|
|00005be0| 20 69 74 20 69 73 20 70 | 6f 73 73 69 62 6c 65 20 | it is p|ossible |
|00005bf0| 74 6f 20 74 75 72 6e 20 | 69 6e 20 74 68 65 20 64 |to turn |in the d|
|00005c00| 69 72 20 64 69 72 65 63 | 74 69 6f 6e 0d 20 20 20 |ir direc|tion.   |
|00005c10| 20 28 75 6e 6c 65 73 73 | 20 28 6f 72 20 28 69 73 | (unless| (or (is|
|00005c20| 2d 6c 65 61 66 20 6e 6f | 64 65 29 0d 20 20 20 20 |-leaf no|de).    |
|00005c30| 20 20 20 20 20 20 20 20 | 20 20 20 20 28 6e 75 6c |        |    (nul|
|00005c40| 6c 20 28 73 65 74 66 20 | 6e 65 77 2d 6e 6f 64 65 |l (setf |new-node|
|00005c50| 20 28 74 75 72 6e 31 20 | 6e 6f 64 65 20 64 69 72 | (turn1 |node dir|
|00005c60| 29 29 29 29 0d 20 20 20 | 20 20 20 28 73 65 74 66 |)))).   |   (setf|
|00005c70| 20 28 62 74 72 61 69 6c | 2d 64 69 72 20 74 65 6d | (btrail|-dir tem|
|00005c80| 70 29 20 64 69 72 29 0d | 20 20 20 20 20 20 28 66 |p) dir).|      (f|
|00005c90| 6f 75 6e 64 2d 6e 6f 64 | 65 20 6e 65 77 2d 6e 6f |ound-nod|e new-no|
|00005ca0| 64 65 20 70 61 74 68 29 | 0d 20 20 20 20 20 20 70 |de path)|.      p|
|00005cb0| 61 74 68 29 29 29 0d 0d | 28 64 65 66 75 6e 20 74 |ath)))..|(defun t|
|00005cc0| 75 72 6e 31 20 28 6e 6f | 64 65 20 64 69 72 29 0d |urn1 (no|de dir).|
|00005cd0| 20 20 28 77 68 65 6e 20 | 6e 6f 64 65 0d 20 20 20 |  (when |node.   |
|00005ce0| 20 28 73 65 6c 65 63 74 | 20 64 69 72 0d 20 20 20 | (select| dir.   |
|00005cf0| 20 20 20 28 2a 6c 65 66 | 74 2a 20 28 62 74 72 65 |   (*lef|t* (btre|
|00005d00| 65 2d 6c 65 66 74 20 6e | 6f 64 65 29 29 0d 20 20 |e-left n|ode)).  |
|00005d10| 20 20 20 20 28 2a 72 69 | 67 68 74 2a 20 20 28 62 |    (*ri|ght*  (b|
|00005d20| 74 72 65 65 2d 72 69 67 | 68 74 20 6e 6f 64 65 29 |tree-rig|ht node)|
|00005d30| 29 0d 20 20 20 20 20 20 | 28 6f 74 68 65 72 77 69 |).      |(otherwi|
|00005d40| 73 65 20 6e 6f 64 65 29 | 29 29 29 0d 0d 28 64 65 |se node)|)))..(de|
|00005d50| 66 75 6e 20 72 65 74 72 | 61 63 74 2d 70 61 74 68 |fun retr|act-path|
|00005d60| 20 28 6b 65 79 20 70 61 | 74 68 20 6f 72 64 65 72 | (key pa|th order|
|00005d70| 2d 66 75 6e 63 74 69 6f | 6e 29 0d 20 20 22 42 61 |-functio|n).  "Ba|
|00005d80| 63 6b 75 70 20 74 68 72 | 6f 75 67 68 20 74 68 65 |ckup thr|ough the|
|00005d90| 20 70 61 74 68 20 62 72 | 61 6e 63 68 20 62 79 20 | path br|anch by |
|00005da0| 62 72 61 6e 63 68 0d 75 | 6e 74 69 6c 20 65 69 74 |branch.u|ntil eit|
|00005db0| 68 65 72 20 74 68 65 20 | 70 61 74 68 20 69 73 20 |her the |path is |
|00005dc0| 65 6d 70 74 79 20 6f 72 | 20 74 68 65 20 6e 6f 64 |empty or| the nod|
|00005dd0| 65 20 77 69 74 68 20 74 | 68 65 20 6b 65 79 20 6c |e with t|he key l|
|00005de0| 69 65 73 20 69 6e 20 74 | 68 65 20 72 6f 6f 74 65 |ies in t|he roote|
|00005df0| 64 20 73 75 62 74 72 65 | 65 22 0d 20 20 28 6c 65 |d subtre|e".  (le|
|00005e00| 74 20 28 74 65 6d 70 20 | 6e 65 77 2d 6b 65 79 20 |t (temp |new-key |
|00005e10| 64 69 72 20 6e 65 77 2d | 6e 6f 64 65 29 0d 20 20 |dir new-|node).  |
|00005e20| 20 20 28 77 68 65 6e 20 | 28 61 6e 64 20 70 61 74 |  (when |(and pat|
|00005e30| 68 20 28 6e 75 6c 6c 20 | 28 62 74 72 61 69 6c 2d |h (null |(btrail-|
|00005e40| 64 69 72 20 28 66 69 72 | 73 74 20 70 61 74 68 29 |dir (fir|st path)|
|00005e50| 29 29 29 0d 20 20 20 20 | 20 20 28 70 6f 70 20 70 |))).    |  (pop p|
|00005e60| 61 74 68 29 29 0d 20 20 | 20 20 28 6c 6f 6f 70 0d |ath)).  |  (loop.|
|00005e70| 20 20 20 20 20 20 28 75 | 6e 6c 65 73 73 20 70 61 |      (u|nless pa|
|00005e80| 74 68 0d 20 20 20 20 20 | 20 20 20 28 72 65 74 75 |th.     |   (retu|
|00005e90| 72 6e 20 70 61 74 68 29 | 29 0d 20 20 20 20 20 20 |rn path)|).      |
|00005ea0| 28 73 65 74 66 20 74 65 | 6d 70 20 28 66 69 72 73 |(setf te|mp (firs|
|00005eb0| 74 20 70 61 74 68 29 0d | 20 20 20 20 20 20 20 20 |t path).|        |
|00005ec0| 20 20 20 20 64 69 72 20 | 28 62 74 72 61 69 6c 2d |    dir |(btrail-|
|00005ed0| 64 69 72 20 74 65 6d 70 | 29 0d 20 20 20 20 20 20 |dir temp|).      |
|00005ee0| 20 20 20 20 20 20 6e 65 | 77 2d 6e 6f 64 65 20 28 |      ne|w-node (|
|00005ef0| 62 74 72 61 69 6c 2d 6e | 6f 64 65 20 74 65 6d 70 |btrail-n|ode temp|
|00005f00| 29 0d 20 20 20 20 20 20 | 20 20 20 20 20 20 6e 65 |).      |      ne|
|00005f10| 77 2d 6b 65 79 20 28 62 | 74 72 65 65 2d 6b 65 79 |w-key (b|tree-key|
|00005f20| 20 6e 65 77 2d 6e 6f 64 | 65 29 29 0d 20 20 20 20 | new-nod|e)).    |
|00005f30| 20 20 28 73 65 6c 65 63 | 74 20 28 66 75 6e 63 61 |  (selec|t (funca|
|00005f40| 6c 6c 20 6f 72 64 65 72 | 2d 66 75 6e 63 74 69 6f |ll order|-functio|
|00005f50| 6e 20 6b 65 79 20 6e 65 | 77 2d 6b 65 79 29 0d 20 |n key ne|w-key). |
|00005f60| 20 20 20 20 20 20 20 28 | 2a 65 71 75 61 6c 2a 0d |       (|*equal*.|
|00005f70| 20 20 20 20 20 20 20 20 | 20 28 72 65 74 75 72 6e |        | (return|
|00005f80| 20 70 61 74 68 29 29 0d | 20 20 20 20 20 20 20 20 | path)).|        |
|00005f90| 28 2a 61 66 74 65 72 2a | 0d 20 20 20 20 20 20 20 |(*after*|.       |
|00005fa0| 20 20 28 75 6e 6c 65 73 | 73 20 28 3d 20 28 66 75 |  (unles|s (= (fu|
|00005fb0| 6e 63 61 6c 6c 20 6f 72 | 64 65 72 2d 66 75 6e 63 |ncall or|der-func|
|00005fc0| 74 69 6f 6e 20 6b 65 79 | 20 28 6d 61 78 2d 76 61 |tion key| (max-va|
|00005fd0| 6c 20 6e 65 77 2d 6e 6f | 64 65 29 29 20 2a 61 66 |l new-no|de)) *af|
|00005fe0| 74 65 72 2a 29 0d 20 20 | 20 20 20 20 20 20 20 20 |ter*).  |        |
|00005ff0| 20 28 75 6e 6c 65 73 73 | 20 28 3d 20 64 69 72 20 | (unless| (= dir |
|00006000| 2a 72 69 67 68 74 2a 29 | 0d 20 20 20 20 20 20 20 |*right*)|.       |
|00006010| 20 20 20 20 20 20 28 72 | 65 74 75 72 6e 20 28 73 |      (r|eturn (s|
|00006020| 65 74 66 20 70 61 74 68 | 20 28 74 75 72 6e 20 70 |etf path| (turn p|
|00006030| 61 74 68 20 2a 72 69 67 | 68 74 2a 29 29 29 29 29 |ath *rig|ht*)))))|
|00006040| 29 0d 20 20 20 20 20 20 | 20 20 28 2a 62 65 66 6f |).      |  (*befo|
|00006050| 72 65 2a 0d 20 20 20 20 | 20 20 20 20 20 28 69 66 |re*.    |     (if|
|00006060| 20 28 3d 20 64 69 72 20 | 2a 65 71 75 61 6c 2a 29 | (= dir |*equal*)|
|00006070| 0d 20 20 20 20 20 20 20 | 20 20 20 20 28 72 65 74 |.       |    (ret|
|00006080| 75 72 6e 20 20 0d 20 20 | 20 20 20 20 20 20 20 20 |urn  .  |        |
|00006090| 20 20 28 69 66 20 28 3d | 20 28 66 75 6e 63 61 6c |  (if (=| (funcal|
|000060a0| 6c 20 6f 72 64 65 72 2d | 66 75 6e 63 74 69 6f 6e |l order-|function|
|000060b0| 20 6b 65 79 20 28 6d 69 | 6e 2d 76 61 6c 20 6e 65 | key (mi|n-val ne|
|000060c0| 77 2d 6e 6f 64 65 29 29 | 20 2a 62 65 66 6f 72 65 |w-node))| *before|
|000060d0| 2a 29 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |*).     |        |
|000060e0| 20 28 73 65 74 66 20 70 | 61 74 68 20 28 74 75 72 | (setf p|ath (tur|
|000060f0| 6e 20 70 61 74 68 20 2a | 6c 65 66 74 2a 29 29 29 |n path *|left*)))|
|00006100| 29 29 29 29 0d 20 20 20 | 20 20 20 28 70 6f 70 20 |)))).   |   (pop |
|00006110| 70 61 74 68 29 29 29 29 | 0d 0d 28 64 65 66 75 6e |path))))|..(defun|
|00006120| 20 72 65 74 72 61 63 74 | 2d 74 6f 2d 72 69 67 68 | retract|-to-righ|
|00006130| 74 20 28 70 61 74 68 29 | 0d 20 20 22 52 65 74 72 |t (path)|.  "Retr|
|00006140| 61 63 74 20 74 68 65 20 | 70 61 74 68 20 74 6f 20 |act the |path to |
|00006150| 74 68 65 20 6e 6f 64 65 | 20 61 73 73 6f 63 69 61 |the node| associa|
|00006160| 74 65 64 20 77 69 74 68 | 20 6e 65 61 72 65 73 74 |ted with| nearest|
|00006170| 20 72 6f 6f 74 65 64 20 | 73 75 62 74 72 65 65 0d | rooted |subtree.|
|00006180| 77 68 6f 73 65 20 6f 72 | 69 67 2d 64 69 72 20 28 |whose or|ig-dir (|
|00006190| 6c 65 66 74 2f 72 69 67 | 68 74 29 20 62 72 61 6e |left/rig|ht) bran|
|000061a0| 63 68 20 68 61 73 20 6e | 6f 74 20 79 65 74 20 62 |ch has n|ot yet b|
|000061b0| 65 65 6e 20 65 78 70 6c | 6f 72 65 64 22 0d 20 20 |een expl|ored".  |
|000061c0| 28 6c 65 74 20 28 74 65 | 6d 70 0d 20 20 20 20 20 |(let (te|mp.     |
|000061d0| 20 20 20 6e 6f 64 65 0d | 20 20 20 20 20 20 20 20 |   node.|        |
|000061e0| 64 69 72 0d 20 20 20 20 | 20 20 20 20 6f 72 69 67 |dir.    |    orig|
|000061f0| 2d 64 69 72 29 0d 20 20 | 20 20 28 6c 6f 6f 70 0d |-dir).  |  (loop.|
|00006200| 20 20 20 20 20 20 64 6f | 20 28 70 6f 70 20 70 61 |      do| (pop pa|
|00006210| 74 68 29 0d 20 20 20 20 | 20 20 77 68 69 6c 65 20 |th).    |  while |
|00006220| 70 61 74 68 0d 20 20 20 | 20 20 20 64 6f 20 28 73 |path.   |   do (s|
|00006230| 65 74 66 20 74 65 6d 70 | 20 28 66 69 72 73 74 20 |etf temp| (first |
|00006240| 70 61 74 68 29 0d 20 20 | 20 20 20 20 20 20 20 20 |path).  |        |
|00006250| 20 20 20 20 20 6e 6f 64 | 65 20 28 62 74 72 61 69 |     nod|e (btrai|
|00006260| 6c 2d 6e 6f 64 65 20 74 | 65 6d 70 29 0d 20 20 20 |l-node t|emp).   |
|00006270| 20 20 20 20 20 20 20 20 | 20 20 20 20 64 69 72 20 |        |    dir |
|00006280| 28 62 74 72 61 69 6c 2d | 64 69 72 20 74 65 6d 70 |(btrail-|dir temp|
|00006290| 29 29 0d 20 20 20 20 20 | 20 75 6e 6c 65 73 73 20 |)).     | unless |
|000062a0| 6f 72 69 67 2d 64 69 72 | 20 64 6f 20 28 73 65 74 |orig-dir| do (set|
|000062b0| 66 20 6f 72 69 67 2d 64 | 69 72 20 64 69 72 29 0d |f orig-d|ir dir).|
|000062c0| 20 20 20 20 20 20 77 68 | 69 6c 65 20 28 61 6e 64 |      wh|ile (and|
|000062d0| 20 28 6e 6f 74 20 28 69 | 73 2d 6c 65 61 66 20 6e | (not (i|s-leaf n|
|000062e0| 6f 64 65 29 29 0d 20 20 | 20 20 20 20 20 20 20 20 |ode)).  |        |
|000062f0| 20 20 20 20 20 20 20 28 | 6e 6f 74 20 28 3d 20 64 |       (|not (= d|
|00006300| 69 72 20 6f 72 69 67 2d | 64 69 72 29 29 0d 20 20 |ir orig-|dir)).  |
|00006310| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 28 |        |       (|
|00006320| 62 74 72 65 65 2d 72 69 | 67 68 74 20 6e 6f 64 65 |btree-ri|ght node|
|00006330| 29 29 29 0d 20 20 20 20 | 70 61 74 68 29 29 0d 0d |))).    |path))..|
|00006340| 3b 3b 20 2d 2d 3e 20 66 | 69 6e 64 20 72 6f 75 74 |;; --> f|ind rout|
|00006350| 69 6e 65 73 0d 0d 0d 0d | 28 64 65 66 75 6e 20 66 |ines....|(defun f|
|00006360| 69 6e 64 2d 6b 65 79 20 | 28 6b 65 79 20 72 6f 6f |ind-key |(key roo|
|00006370| 74 20 6f 72 64 65 72 2d | 66 75 6e 63 74 69 6f 6e |t order-|function|
|00006380| 29 0d 20 20 22 47 69 76 | 65 6e 20 74 68 65 20 6b |).  "Giv|en the k|
|00006390| 65 79 2c 20 74 68 65 20 | 72 6f 6f 74 20 6f 66 20 |ey, the |root of |
|000063a0| 61 20 62 74 72 65 65 20 | 61 6e 64 20 74 68 65 20 |a btree |and the |
|000063b0| 6f 72 64 65 72 2d 66 75 | 6e 63 74 69 6f 6e 20 66 |order-fu|nction f|
|000063c0| 6f 72 20 6b 65 79 20 63 | 6f 6d 70 61 72 69 73 6f |or key c|ompariso|
|000063d0| 6e 3a 0d 72 65 74 75 72 | 6e 20 74 68 65 20 76 61 |n:.retur|n the va|
|000063e0| 6c 75 65 20 6f 66 20 74 | 68 65 20 6e 6f 64 65 20 |lue of t|he node |
|000063f0| 61 73 73 6f 63 69 61 74 | 65 64 20 77 69 74 68 20 |associat|ed with |
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.